1 #include <cstdio> 2 int root,N=0,n,p,q; 3 int fa[100001],c[100001][2],size[100001],sp[100001]; 4 void rot(int x) 5 { 6     int y=fa[x],k=(c[y][0]==x); 7     size[y]=size[c[y][k]]+size[c[x][k]]+1;size[x]=size[c[x][!k]]+size[y]+1; 8     c[y][!k]=c[x][k];fa[c[y][!k]]=y; 9     fa[x]=fa[y];if(fa[y])c[fa[y]][c[fa[y]][1]==y]=x;10     c[x][k]=y;fa[y]=x;11 }12 void rots(int x,int g)13 {14     for(int y=fa[x];y!=g;rot(x),y=fa[x])15     if(fa[y]!=g)    rot((x==c[y][0])==(y==c[fa[y]][0])?y:x);16     if(g==0) root=x;17 }18 void insert(int x)19 {20     int y=root;21     while(c[y][x>sp[y]]) y=c[y][x>sp[y]];22     sp[++N]=x;c[N][0]=c[N][1]=0;fa[N]=y;if(y)c[y][x>sp[y]]=N;23     rots(N,0);24 }25 void del(int x)26 {27     int y=root;28     while(sp[y]!=x) y=c[y][x>sp[y]];29     rots(y,0);y=c[root][1];30     bool b;31     if(!y) b=1,y=c[root][0];else b=0;32     while(c[y][b]) y=c[y][b];33     rots(y,root);34     c[y][b]=c[root][b];fa[c[root][b]]=y;fa[y]=0;root=y;35     size[y]=size[c[y][!b]]+size[c[y][b]];36 }37 int rank(int x)38 {39     int y=root,ans=0;40     if(x==918145){41         printf("");42     }43     while(y)44         if(x>sp[y])45             ans+=size[c[y][0]]+1,y=c[y][1];46         else y=c[y][0];47     return ans+1;48 }49 int num(int x)50 {51     int y=root;52     while(x)53     if(size[c[y][0]]+1<x)54         x-=size[c[y][0]]+1,y=c[y][1];55     else if(size[c[y][0]]+1==x) return sp[y];56     else y=c[y][0];57     return sp[y];58 }59 int pre(int x)60 {61     int ans;62     for(int y=root;y;)63     if(sp[y]<x)64         ans=sp[y],y=c[y][1];65     else y=c[y][0];66     return ans;67 }68 int nex(int x)69 {70     int ans;71     for(int y=root;y;)72     if(sp[y]<=x)73         y=c[y][1];74     else ans=sp[y],y=c[y][0];75     return ans;76 }77 int main()78 {79     freopen("1.out","w",stdout);80     scanf("%d",&n);81     for(int i=1;i<=n;i++)82     {83         scanf("%d%d",&p,&q);84         if(p==1) insert(q);85         if(p==2) del(q);86         if(p==3) printf("%d\n",rank(q));87         if(p==4) printf("%d\n",num(q));88         if(p==5) printf("%d\n",pre(q));89         if(p==6) printf("%d\n",nex(q));90     }91     return 0;92 }