treap模板（tyvj普通二叉树）

模板题。。。
#include <cassert>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
#define INF 0x3fffffff
struct Treap
{
struct node{int v,tot,sz,rnd,ch[2];}t;
int sz,root,tmp;
void init(long long int n){t=(node)malloc(sizeof(node)*n+10);}
void update(int x){t[x].sz=t[t[x].ch[0]].sz+t[t[x].ch[1]].sz+t[x].tot;}
void turn(int &x,int k)
{
int y=t[x].ch[k^1];
t[x].ch[k^1]=t[y].ch[k];
t[y].ch[k]=x;
update(x);
update(y);
x=y;
}
void insert(int &x,int v)
{
if(!x)
t[++sz].v=v,t[sz].rnd=rand(),t[sz].tot=t[sz].sz=1,x=sz;
else{
if(t[x].sz++,t[x].v==v)t[x].tot++;
else if(insert(t[x].ch[tmp=v>t[x].v],v),t[t[x].ch[tmp]].rnd>t[x].rnd)turn(x,tmp^1);
}
}
void del(int &x,int v)
{
if(!x)return;
if(t[x].v==v){
if(t[x].tot>1)t[x].tot--,t[x].sz--;
else{
if(!(t[x].ch[0]&&t[x].ch[1]))x=t[x].ch[0]|t[x].ch[1];
else turn(x,tmp=t[t[x].ch[0]].rnd>t[t[x].ch[1]].rnd),t[x].sz--,del(t[x].ch[tmp],v);
}
}
else
t[x].sz--,del(t[x].ch[v>t[x].v],v);
}
int askRank(int x,int v)
{
if(t[x].v==v)return t[t[x].ch[0]].sz+1;
if(t[x].v<v)return t[t[x].ch[0]].sz+t[x].tot+askRank(t[x].ch[1],v);
else return askRank(t[x].ch[0],v);
}
int askKth(int x,int v)
{
if(!x)return 0;
if(v<=t[t[x].ch[0]].sz)return askKth(t[x].ch[0],v);
else if(v>t[t[x].ch[0]].sz+t[x].tot)return askKth(t[x].ch[1],v-t[t[x].ch[0]].sz-t[x].tot);
else return t[x].v;
}
int pre(int v)
{
insert(root,v);
tmp=askKth(root,askRank(root,v)-1);
del(root,v);
return tmp;
}
int find(int x,int v){return t[x].v==v?x:find(t[x].ch[t[x].v<v],v);}
int sub(int v)
{
insert(root,v);
tmp=askKth(root,askRank(root,v)+t[find(root,v)].tot);
del(root,v);
return tmp;
}
}treap;
int main()
{
int n;
scanf("%d",&n);
treap.init(n);
while(n--)
{
int a,b;
scanf("%d%d",&a,&b);
switch(a)
{
case 1:treap.insert(treap.root,b);break;//1. 插入x数
case 2:treap.del(treap.root,b);break;//2. 删除x数(若有多个相同的数，因只删除一个)
case 3:printf("%d\n",treap.askRank(treap.root,b));break;//3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
case 4:printf("%d\n",treap.askKth(treap.root,b));break;//4. 查询排名为x的数
case 5:printf("%d\n",treap.pre(b));break;//5. 求x的前驱(前驱定义为小于x，且最大的数)
case 6:printf("%d\n",treap.sub(b));break;//6. 求x的后继(后继定义为大于x，且最小的数)
}
}
}