Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1 插入x数
2 删除x数(若有多个相同的数，因只删除一个)
3 查询x数的排名(排名定义为比当前数小的数的个数+1+1。若有多个相同的数，因输出最小的排名)
4 查询排名为x的数
5 求x的前驱(前驱定义为小于x，且最大的数)
6 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1≤opt≤6)。
Output
对于操作3,4,5,6每行输出一个数，表示对应答案。
Hint
n<=100000
Solution
打标的地方是错了的细节。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 100005
#define inf 0x3f3f3f3f
struct Splay_Tree{
int FA;
int data;
int ch[2];
int num;
int size;
}t[maxn];
int node,n,x,y,root;
void Rotate(int x){
int y=t[x].FA,z=t[y].FA,k=(x==t[y].ch[1]);
t[z].ch[t[z].ch[1]==y]=x;
t[x].FA=z;
t[y].ch[k]=t[x].ch[k^1];
t[t[x].ch[k^1]].FA=y;
t[x].ch[k^1]=y;
t[y].FA=x;
t[y].size=t[t[y].ch[1]].size+t[t[y].ch[0]].size+t[y].num;
t[x].size=t[t[x].ch[1]].size+t[t[x].ch[0]].size+t[x].num;
}
void Splay_S(int x,int destnation){
int y,z;
while(t[x].FA!=destnation){
y=t[x].FA,z=t[y].FA;
if(z!=destnation){
(x==t[y].ch[0])^(y==t[z].ch[0])?Rotate(x):Rotate(y);
}
Rotate(x);
}
if(destnation==0)root=x;
}
int find(int x){
int u=root;
if(!u)return -1;
while(t[u].ch[x>t[u].data]&&x!=t[u].data){
u=t[u].ch[x>t[u].data];//
}
Splay_S(u,0);
return u;
}
void Insert_n(int x){
int u=root,fa=0;
while(u&&t[u].data!=x){
fa=u;
u=t[u].ch[x>t[u].data];
}
if(u){
t[u].num++;
}
else{
u=++node;
if(fa)t[fa].ch[x>t[fa].data]=u;
t[u].ch[0]=t[u].ch[1]=0;
t[u].FA=fa;
t[u].data=x;
t[u].num=1;
t[u].size=1;
}
Splay_S(u,0);
}
int Next_N(int x,bool flag){
int u=find(x);
if(t[u].data<x&&!flag)return u;//
if(t[u].data>x&&flag)return u;
u=t[u].ch[flag];
while(t[u].ch[flag^1]){
u=t[u].ch[flag^1];
}
return u;
}
void Delet_e(int x){
int Pre_X=Next_N(x,0);
int Suc_X=Next_N(x,1);
Splay_S(Pre_X,0);//
Splay_S(Suc_X,Pre_X);
int p=t[Suc_X].ch[0];
if(t[p].num>1){
t[p].num--;
Splay_S(p,0);
}
else t[Suc_X].ch[0]=0;
}
int kth(int k){
int u=root;
if(t[u].size<k)return -1;
while(1){
if(t[t[u].ch[0]].size>=k)u=t[u].ch[0];//
else{
if(t[t[u].ch[0]].size+t[u].num>=k)return u;
else{
k=k-t[t[u].ch[0]].size-t[u].num;
u=t[u].ch[1];
}
}
}
}
int main(){
Insert_n(inf);//
Insert_n(-inf);//
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
if(x==1){
Insert_n(y);
}
else if(x==2){
Delet_e(y);
}
else if(x==3){
printf("%d
",t[t[find(y)].ch[0]].size);//
}
else if(x==4){
printf("%d
",t[kth(y+1)].data);
}
else if(x==5){
printf("%d
",t[Next_N(y,0)].data);
}
else if(x==6){
printf("%d
",t[Next_N(y,1)].data);
}
}
return 0;
}