Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
84185
492737
HINT
1.n的数据范围：n<=100000
2.每个数的数据范围：[-1e7,1e7]
数据如下http://pan.baidu.com/s/1jHMJwO2
Source
平衡树
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
treap~
个人理解：是一种用随机的rank值来给子节点排序，使得树较为平衡的平衡树。父节点rank小于子节点，且右儿子val>父节点val>左儿子val。每个节点代表多个val相同的点。
注意：1.注释处要+1；
2.ins()中!u时及时返回；
3.last和next不能互相嵌套；
4.rand()函数开头文件cstdlib和ctime.
#include<cstdio>
#include<cstdlib>
#include<ctime>int n,x,y,ans,root,cnt;struct node{int l,r,siz,w,v,rank;
}a[100001];int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}void update(int u)
{a[u].siz=a[a[u].l].siz+a[a[u].r].siz+a[u].w;
}void lturn(int &u)
{int k=a[u].r;a[u].r=a[k].l;a[k].l=u;a[k].siz=a[u].siz;update(u);u=k;
}void rturn(int &u)
{int k=a[u].l;a[u].l=a[k].r;a[k].r=u;a[k].siz=a[u].siz;update(u);u=k;
}void ins(int &k,int v)
{if(!k){k=++cnt;a[k].siz=a[k].w=1;a[k].v=v;a[k].rank=rand();return;}a[k].siz++;if(v==a[k].v) a[k].w++;else if(v<a[k].v){ins(a[k].l,v);if(a[k].rank>a[a[k].l].rank) rturn(k);}else{ins(a[k].r,v);if(a[k].rank>a[a[k].r].rank) lturn(k);}
}void del(int &k,int v)
{if(!k) return;if(a[k].v==v){if(a[k].w>1) a[k].w--,a[k].siz--;else if(!(a[k].l*a[k].r)) k=a[k].l+a[k].r;else if(a[a[k].l].rank<a[a[k].r].rank) rturn(k),del(k,v);else lturn(k),del(k,v);}else if(v<a[k].v) a[k].siz--,del(a[k].l,v);else a[k].siz--,del(a[k].r,v);
}int cal_rank(int k,int v)
{if(!k) return 0;if(a[k].v==v) return a[a[k].l].siz+1; //+1!else if(v<a[k].v) return cal_rank(a[k].l,v);else return a[a[k].l].siz+a[k].w+cal_rank(a[k].r,v);
}int cal_num(int k,int v)
{if(!k) return 0;if(a[a[k].l].siz>=v) return cal_num(a[k].l,v);if(a[a[k].l].siz+a[k].w<v) return cal_num(a[k].r,v-a[a[k].l].siz-a[k].w);return a[k].v;
}void last(int k,int v)
{if(!k) return;if(a[k].v<v) ans=a[k].v,last(a[k].r,v);else last(a[k].l,v);
}void next(int k,int v)
{if(!k) return;if(a[k].v>v) ans=a[k].v,next(a[k].l,v);else next(a[k].r,v);
}int main()
{n=read();while(n--){x=read();y=read();switch(x){case(1):ins(root,y);break;case(2):del(root,y);break;case(3):printf("%d\n",cal_rank(root,y));break;case(4):printf("%d\n",cal_num(root,y));break;case(5):last(root,y);printf("%d\n",ans);break;case(6):next(root,y);printf("%d\n",ans);break;}}return 0;
}