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
Sample Output
106465
84185
492737
HINT
1.n的数据范围：n<=100000
2.每个数的数据范围：[-2e9,2e9]
题解
省选前复习模板系列
Splay直接上
一遍过美滋滋
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{int f,n,c,d,son[2];
}tr[111000];int len,root;
void add(int d,int f)
{len++;tr[len].d=d;tr[len].f=f;tr[len].c=tr[len].n=1;tr[len].son[0]=tr[len].son[1]=0;if(d<tr[f].d)tr[f].son[0]=len;else tr[f].son[1]=len;
}
void upd(int now){
tr[now].c=tr[tr[now].son[0]].c+tr[tr[now].son[1]].c+tr[now].n;}
void rotate(int x,int w)
{int R,r;int f=tr[x].f,ff=tr[f].f;R=f;r=tr[x].son[w];tr[R].son[1-w]=r;if(r!=0)tr[r].f=R;R=ff;r=x;if(tr[R].son[0]==f)tr[R].son[0]=x;else tr[R].son[1]=x;tr[r].f=R;R=x;r=f;tr[R].son[w]=r;tr[r].f=R;upd(f);upd(x);
}
void splay(int x,int rt)
{while(tr[x].f!=rt){int f=tr[x].f,ff=tr[f].f;if(ff==rt){if(tr[f].son[0]==x)rotate(x,1);else rotate(x,0);}else{if(tr[ff].son[0]==f && tr[f].son[0]==x)rotate(f,1),rotate(x,1);else if(tr[ff].son[1]==f && tr[f].son[0]==x)rotate(x,1),rotate(x,0);else if(tr[ff].son[1]==f && tr[f].son[1]==x)rotate(f,0),rotate(x,0);else rotate(x,0),rotate(x,1);}}if(rt==0)root=x;
}
int findip(int d)
{int x=root;while(1){if(d<tr[x].d){if(tr[x].son[0]!=0)x=tr[x].son[0];else return x;}else if(d>tr[x].d){if(tr[x].son[1]!=0)x=tr[x].son[1];else return x;}else return x;}
}
void ins(int d)
{if(root==0){add(d,0);root=len;return ;}int x=findip(d);if(tr[x].d==d){
tr[x].n++;upd(x);splay(x,0);}else{add(d,x);upd(x);splay(len,0);}
}
void del(int d)
{int x=findip(d);splay(x,0);if(tr[x].n>1){
tr[x].n--;upd(x);return ;}else if(tr[x].son[0]==0 && tr[x].son[1]==0){root=len=0;return ;}else if(tr[x].son[0]==0 && tr[x].son[1]!=0){root=tr[x].son[1];tr[root].f=0;return ;}else if(tr[x].son[0]!=0 && tr[x].son[1]==0){root=tr[x].son[0];tr[root].f=0;return ;}else{int p=tr[x].son[0];while(tr[p].son[1]!=0)p=tr[p].son[1];splay(p,x);tr[p].son[1]=tr[x].son[1];tr[tr[x].son[1]].f=p;root=p;tr[root].f=0;upd(p);}
}
int findrank(int d)//找d的排名
{int x=findip(d);splay(x,0);return tr[tr[x].son[0]].c+1;
}
int findKth(int K)//找排名为K的数
{int x=root;while(1){int lc=tr[x].son[0],rc=tr[x].son[1];if(K<=tr[lc].c)x=lc;else if(K>tr[lc].c+tr[x].n)K-=tr[lc].c+tr[x].n,x=rc;else return tr[x].d;}
}
int findpre(int d)
{int x=findip(d);splay(x,0);if(d<=tr[x].d){x=tr[x].son[0];while(tr[x].son[1]!=0)x=tr[x].son[1];}return tr[x].d;
}
int findnxt(int d)
{int x=findip(d);splay(x,0);if(d>=tr[x].d){x=tr[x].son[1];while(tr[x].son[0]!=0)x=tr[x].son[0];}return tr[x].d;
}
int T;
int main()
{scanf("%d",&T);root=len=0;while(T--){int op,x;scanf("%d%d",&op,&x);if(op==1)ins(x);else if(op==2)del(x);else if(op==3)printf("%d\n",findrank(x));else if(op==4)printf("%d\n",findKth(x));else if(op==5)printf("%d\n",findpre(x));else printf("%d\n",findnxt(x));}return 0;
}