danihao123's Blog

很好，这很interesting。

最大坑点是数可能重复。然后前驱后驱赶脚也挺坑的……

还有好像BZOJ不滋磁time(0)哎。所以我就用了wyy的生日做随机数种子辣！

代码：

/**************************************************************
    Problem: 3224
    User: danihao123
    Language: C++
    Result: Accepted
    Time:376 ms
    Memory:1880 kb
****************************************************************/
 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
struct Node{
    Node *ch[2];
    int v;
    int r;
    int s;
    int cnt;
    Node(){
        v=s=cnt=0;
        r=-1;
        ch[0]=ch[1]=NULL;
    }
    Node(int key,Node *lc,Node *rc){
        v=key;
        r=rand();
        s=1;
        cnt=1;
        ch[0]=lc;
        ch[1]=rc;
    }
    void maintain(){
        s=ch[0]->s+ch[1]->s+cnt;
    }
};
struct Treap{
    Node *null,*root;
    Treap(){
        null=new Node();
        root=null;
    }
    void rotate(Node* &o,int d){
        Node* k=o->ch[d^1];
        o->ch[d^1]=k->ch[d];
        k->ch[d]=o;
        o->maintain();
        k->maintain();
        o=k;
    }
    void insert(Node* &o,int x){
        if(o==null){
            o=new Node(x,null,null);
        }else{
            if(o->v==x){
                o->cnt++;
                o->s++;
            }else{
                int d=x>(o->v);
                insert(o->ch[d],x);
                if(((o->ch[d])->r)>(o->r))
                    rotate(o,d^1);
            }
        }
        o->maintain();
    }
    void del(Node* &o,int x){
        if(o->v==x){
            if(o->cnt>1){
                o->cnt--;
                o->s--;
            }else{
                if(o->ch[0]==null){
                    Node *u=o;
                    o=o->ch[1];
                    delete u;
                }else{
                    if(o->ch[1]==null){
                        Node *u=o;
                        o=o->ch[0];
                        delete u;
                    }else{
                        int d=(o->ch[1]->r)>(o->ch[0]->r);
                        rotate(o,d^1);
                        del(o->ch[d^1],x);
                    }
                }
            }
        }else{
            int d=x>(o->v);
            del(o->ch[d],x);
        }
        if(o!=null)
            o->maintain();
    }
    int kth(Node *o,int k){
        if(k<=(o->ch[0]->s)){
            return kth(o->ch[0],k);
        }else{
            k-=o->ch[0]->s;
            if(k<=o->cnt)
                return o->v;
            else
                return kth(o->ch[1],k-(o->cnt));
        }
    }
    int rank(Node *o,int x){
        if(o==null)
            return 0;
        if(x<(o->v)){
            return rank(o->ch[0],x);
        }else{
            if(x==o->v)
                return o->ch[0]->s+1;
            else
                return o->ch[0]->s+o->cnt+rank(o->ch[1],x);
        }
    }
    int pre(int x){
        Node *cur=root;
        int ans=0;
        while(cur!=null){
            if(cur->v<x){
                ans=cur->v;
                cur=cur->ch[1];
            }else{
                cur=cur->ch[0];
            }
        }
        return ans;
    }
    int suc(int x){
        Node *cur=root;
        int ans=0;
        while(cur!=null){
            if(cur->v>x){
                ans=cur->v;
                cur=cur->ch[0];
            }else{
                cur=cur->ch[1];
            }
        }
        return ans;
    }
};
int main(){
    int n;
    int opt,x;
    Treap T;
    scanf("%d",&n);
    srand(20020601);
    while(n--){
        scanf("%d%d",&opt,&x);
        if(opt==1){
            T.insert(T.root,x);
        }else{
            if(opt==2){
                T.del(T.root,x);
            }else{
                if(opt==3){
                    printf("%d\n",T.rank(T.root,x));
                }else{
                    if(opt==4){
                        printf("%d\n",T.kth(T.root,x));
                    }else{
                        if(opt==5){
                            printf("%d\n",T.pre(x));
                        }else{
                            printf("%d\n",T.suc(x));
                        }
                    }
                }
            }
        }
    }
    return 0;
}