巴蜀1322 第k小的数

#include<cstdio>
#include<cstdlib>
struct node
{int size,x,v,k[2];
}t[3100000];
int root,size;
void up(int p)
{t[p].size=t[t[p].k[0]].size+t[t[p].k[1]].size+1;
}
void rot(int &p,bool b)
{int x=t[p].k[b];int y=t[x].k[!b];t[p].k[b]=y;t[x].k[!b]=p;up(p);up(x);p=x;
}
void ins(int &p,int x)
{if (p==0){p=++size;t[p].x=x;t[p].v=rand();t[p].size=1;return;}if (t[p].x==x) return;bool b=x>t[p].x;ins(t[p].k[b],x);up(p);if (t[t[p].k[b]].v>t[p].v)rot(p,b);
}
void del(int &p,int x)
{if (p==0) return;if (t[p].x==x){if (t[p].k[0]==0&&t[p].k[1]==0){p=0;return;}bool b=t[t[p].k[0]].v<t[t[p].k[1]].v;rot(p,b);del(t[p].k[!b],x);up(p);}del(t[p].k[x>t[p].x],x);up(p);
}
int find(int p,int x)
{if (p==0) return 0;if (t[t[p].k[0]].size>=x) return find(t[p].k[0],x);if (t[t[p].k[0]].size+1==x) return t[p].x;return find(t[p].k[1],x-t[t[p].k[0]].size-1);
}
int main()
{int m,n,i,j,k,x,y,z;scanf("%d%d",&n,&m);for (i=1;i<=n;i++){scanf("%d",&x);ins(root,x);}for (i=1;i<=m;i++){scanf("%d%d",&x,&y);if (x==1) ins(root,y);if (x==2) del(root,y);if (x==3) printf("%d\n",find(root,y));}
}