P3369 【模板】普通平衡树 (fhq treap)

2018-01-04 14:10:17


传送门:http://www.yhzq-blog.cc/fhq-treap%E6%80%BB%E7%BB%93/

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    const int maxn=100010;
    int n;
    inline int read(){
        int ret=0,s=1;
        char ch=getchar();
        while(ch<'0'||ch>'9') {if(ch=='-') s=-1; ch=getchar();}
        while(ch>='0'&&ch<='9') {ret=ret*10+ch-'0'; ch=getchar();}
        return ret*s;
    }
    int root,Tcnt;
    struct node{
        int son[2],val,prio,size;
        node(){}
        node(int x){son[0]=son[1]=0,val=x,prio=rand(),size=1;}
    }T[maxn];
    inline void pushup(int u){T[u].size=T[T[u].son[0]].size+T[T[u].son[1]].size+1;}
    void split(int u,int k,int &x,int &y){
        if(!u) {x=y=0; return;}
        else if(T[u].val<=k) x=u,split(T[u].son[1],k,T[u].son[1],y);
        else y=u,split(T[u].son[0],k,x,T[u].son[0]);
        pushup(u);
    }
    int merge(int x,int y){
        if(!x||!y) return x+y;
        else if(T[x].prio<T[y].prio){
            T[x].son[1]=merge(T[x].son[1],y);
            pushup(x);
            return x;
        }
        else{
            T[y].son[0]=merge(x,T[y].son[0]);
            pushup(y);
            return y;
        }
    }
    inline void ins(int x){
        int a,b;
        split(root,x,a,b);
        T[++Tcnt]=node(x);
        root=merge(merge(a,Tcnt),b);
    }
    inline void del(int x){
        int a,b,c;
        split(root,x,a,b);
        split(a,x-1,a,c);
        root=merge(merge(a,merge(T[c].son[0],T[c].son[1])),b);
    }
    inline int rank(int x){
        int a,b,ret;
        split(root,x-1,a,b);
        ret=T[a].size+1;
        root=merge(a,b);
        return ret;
    }
    inline int num(int x){
        int u=root;
        while(1){
            int lsize=T[T[u].son[0]].size;
            if(x==lsize+1) return T[u].val;
            else if(x<=lsize) u=T[u].son[0];
            else u=T[u].son[1],x-=lsize+1;
        }
    }
    inline int pre(int x){
        int a,b;
        split(root,x-1,a,b);
        int u=a,ret;
        while(T[u].son[1]) u=T[u].son[1];
        ret=T[u].val;
        root=merge(a,b);
        return ret;
    }
    inline int nxt(int x){
        int a,b;
        split(root,x,a,b);
        int u=b,ret;
        while(T[u].son[0]) u=T[u].son[0];
        ret=T[u].val;
        root=merge(a,b);
        return ret;
    }
    int main(){
        srand(1);
        n=read();
        for(int i=1;i<=n;i++){
            int op=read(),x=read();
            switch(op){
                case 1:{
                    ins(x);
                    break;
                }
                case 2:{
                    del(x);
                    break;
                }
                case 3:{
                    printf("%d\n",rank(x));
                    break;
                }
                case 4:{
                    printf("%d\n",num(x));
                    break;
                }
                case 5:{
                    printf("%d\n",pre(x));
                    break;
                }
                default:{
                    printf("%d\n",nxt(x));
                    break;
                }
            }
        }
        return 0;
    }