1 #include "bits/stdc++.h" 2  3 using namespace std; 4  5 inline int read(){ 6     int s=0,k=1;char ch=getchar(); 7     while(ch<'0'|ch>'9') ch=='-'?k=-1:0,ch=getchar(); 8     while(ch>47&ch<='9') s=s*10+(ch^48),ch=getchar(); 9     return s*k;10 }11 12 const int N=1e5+5,inf=0x7fffffff;13 14 #define size(t) (t?t->size:0)15 16 struct Treap{17     Treap *son[2];18     int fix,val,size;19     Treap (int v){20         size=1,val=v,fix=rand();21         son[0]=son[1]=NULL;22     }23     inline void update(){24         size=1+size(son[0])+size(son[1]);25     }26 }*root;27 28 typedef pair
     
       D;29 30 inline Treap *merge(Treap *a,Treap *b){31     if(!a||!b) return a?a:b;32     if(a->fix
      
       fix){33         a->son[1]=merge(a->son[1],b);a->update();return a;34     }else   {35         b->son[0]=merge(a,b->son[0]);b->update();return b;36     }37 }38 39 inline D split(Treap *p,int k){40     if(!p)  return D(NULL,NULL);41     D y;42     if(size(p->son[0])>=k) 43         y=split(p->son[0],k),p->son[0]=y.second,p->update(),y.second=p;44     else45         y=split(p->son[1],k-1-size(p->son[0])),p->son[1]=y.first,p->update(),y.first=p;46     return y;47 }48 49 inline int get_rnk(int val){50     int ret=0;51     for(Treap *t=root;t;t=t->son[val>t->val])52         if(t->val
       
        son[0]);53     return ret;54 }55 56 inline int findkth(int k){57     D x=split(root,k-1);58     D y=split(x.second,1);59     Treap *ans=y.first;60     root=merge(merge(x.first,ans),y.second);61     return ans?ans->val:0;62 }63 64 inline void insert(int val){65     int k=get_rnk(val);66     D x=split(root,k);67     Treap *p=new Treap(val);68     root=merge(merge(x.first,p),x.second);69 }70 71 inline void erase(int val){72     int k=get_rnk(val);73     D x=split(root,k);74     D y=split(x.second,1);75     root=merge(x.first,y.second);76 }77 78 int main(){    79     freopen("phs.in","r",stdin);80     freopen("phs.out","w",stdout);81     srand(1228);82     int m,opt,x;m=read();83     while(m--){84         opt=read(),x=read();85         switch(opt)86         {87             case 1:insert(x);break;88             case 2:erase(x);break;89             case 3:printf("%d\n",get_rnk(x)+1);break;90             case 4:printf("%d\n",findkth(x));break;91             case 5:printf("%d\n",findkth(get_rnk(x)));break;92             case 6:printf("%d\n",findkth(get_rnk(x+1)+1));break;93         }94     }95 }