splay普通平衡樹coedvs4543

題目描述

您需要寫一種資料結構（可參考題目标題），來維護一些數，其中需要提供以下操作：

插入x數

删除x數(若有多個相同的數，因隻删除一個)

查詢x數的排名(排名定義為比目前數小的數的個數+1。若有多個相同的數，因輸出最小的排名)

查詢排名為x的數

求x的前驅(前驅定義為小于x，且最大的數)

求x的後繼(後繼定義為大于x，且最小的數)

輸入輸出格式

輸入格式：

第一行為n，表示操作的個數,下面n行每行有兩個數opt和x，opt表示操作的序号( 1 \leq opt \leq 6 1≤opt≤6 )

輸出格式：

對于操作3,4,5,6每行輸出一個數，表示對應答案

輸入輸出樣例

輸入樣例#1：

10

1 106465

4 1

1 317721

1 460929

1 644985

1 84185

1 89851

6 81968

1 492737

5 493598

輸出樣例#1：

106465

84185

492737

說明

時空限制：1000ms,128M

來源：Tyvj1728 原名：普通平衡樹

注意細節

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=;
int size[MAXN],f[MAXN],key[MAXN],cnt[MAXN],ch[MAXN][];
int root = ,n,sz = ;
void up(int x)
{
    if(x)
    {
        size[x]=cnt[x];
        if(ch[x][]) size[x]+=size[ch[x][]];
        if(ch[x][]) size[x]+=size[ch[x][]];
        return;
    }
}
void clear(int x)
{
    key[x]=cnt[x]=f[x]=size[x]=cnt[x]=ch[x][]=ch[x][]=;
    return;
}
bool get(int x)
{
    return ch[f[x]][]==x;
}
void rotate(int x)
{
    int y=f[x],z=f[y],k=get(x);
    ch[y][k]=ch[x][k^];
    f[ch[y][k]]=y;
    ch[x][k^]=y;
    f[x]=z;
    f[y]=x;
    if(z) ch[z][ch[z][]==y]=x;
    up(y),up(x);
    return;
}
void splay(int x)
{
    for(int fa;fa=f[x];rotate(x))
    if(f[fa]) rotate(get(x)==get(fa)?fa:x);
    root=x;//别忘了
    return;
}
void insert(int x)
{
    if(root==) 
    {
        sz++;
        size[sz]=cnt[sz]=;
        ch[sz][]=ch[sz][]=;
        f[sz]=;
        root=sz;//别忘了
        key[sz]=x;
        return;
    }
    int now=root,fa=;
    while(true)
    {
        if(x==key[now])
        {
            cnt[now]++;
            up(now),up(fa);
            splay(now);
            break;
        }
        fa=now;
        now=ch[now][key[now]<x];
        if(!now)
        {
            sz++;
            ch[sz][]=ch[sz][]=;
            f[sz]=fa;
            size[sz]=cnt[sz]=;
            ch[fa][key[fa]<x]=sz;//！！！！！别忘了！！！！！！
            key[sz]=x;
            up(fa);
            splay(sz);
            break;
        }
    }
    return;
}
int find(int x)
{
    int now=root,ans=;
    while(true)
    {
        if(x<key[now]) now=ch[now][];
        else 
        {
            ans+=(ch[now][]?size[ch[now][]]:);
            if(x==key[now])
            {
                splay(now);
                return ans+;
            }
            ans+=cnt[now];
            now=ch[now][];
        } 
    }
}
int findx(int x)
{
    int now=root;
    while(true)
    {
        if(ch[now][] && x<=size[ch[now][]]) now=ch[now][];
        else 
        {
            int temp=(ch[now][]?size[ch[now][]]:)+cnt[now];
            if(x<=temp) return key[now];
            x-=temp;
            now=ch[now][];
        }
    }
}
int pre()
{
    int now=ch[root][];
    while(ch[now][]) now=ch[now][];
    return now;
}
int nxt()
{
    int now=ch[root][];
    while(ch[now][]) now=ch[now][];
    return now;
}
void del(int x)
{
    int ss=find(x);
    if(cnt[root]>)
    {
        cnt[root]--;
        up(root);
        return;
    }
    if(!ch[root][] && !ch[root][])
    {
        clear(root);
        root=;
        return;
    }
    if(!ch[root][]) 
    {
        int t=root;
        root=ch[root][];
        f[root]=;
        clear(t);
        return;
    }
    if(!ch[root][])
    {
        int t=root;
        root=ch[root][];
        f[root]=;
        clear(t);
        return;
    }
    int ll=pre(),y=root;//!!!!!!
    splay(ll);
    ch[root][]=ch[y][];
    f[ch[y][]]=root;
    clear(y);
    up(root);
    return;
}
int main()
{
    int opt,x;
    cin>>n;
    for(int i=;i<=n;i++)
    {
        scanf("%d%d",&opt,&x);
        switch(opt)
        {
            case :insert(x);break;
            case :del(x);break;
            case :printf("%d\n",find(x));break;
            case :printf("%d\n",findx(x));break;
            case :insert(x);printf("%d\n",key[pre()]),del(x);break;
            case :insert(x);printf("%d\n",key[nxt()]),del(x);break;
        }
    }
    return ;
}