您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)

对于操作3,4,5,6每行输出一个数，表示对应答案

平衡树

  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 using namespace std;  9 const int mxn=120010; 10 int read(){ 11     int x=0,f=1;char ch=getchar(); 12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 14     return x*f; 15 } 16 struct node{ 17     int l,r; 18     int val,sz; 19     int cnt; 20     bool operator < (const node b)const{ 21         return val<b.val; 22     } 23 }t[mxn],vt[mxn]; 24 int rot=0; 25 int sz=0,cnt=0; 26 int st[mxn],top=0; 27 int flag=0,faf; 28 int newnode(){ 29     int res=0; 30     if(top)res=st[top--]; 31     else res=++cnt; 32     t[res].sz=t[res].l=t[res].r=t[res].cnt=0; 33     return res; 34 } 35 void pushup(int x){ 36     t[x].sz=t[t[x].l].sz+t[t[x].r].sz+t[x].cnt;return; 37 } 38 void Build(int l,int r,int &rt){ 39     if(l>r){rt=0;return;} 40     int mid=(l+r)>>1; 41     rt=newnode(); 42     t[rt].val=vt[mid].val; 43     t[rt].cnt=vt[mid].cnt; 44     t[rt].sz=t[rt].cnt; 45     Build(l,mid-1,t[rt].l); 46     Build(mid+1,r,t[rt].r); 47     pushup(rt); 48     return; 49 } 50 void insert(int &rt,int x){ 51     if(!rt){ 52         rt=newnode(); 53         t[rt].val=x; 54         t[rt].cnt=t[rt].sz=1; 55         return; 56     } 57     t[rt].sz++; 58     if(t[rt].val==x){ 59         t[rt].cnt++; 60         return; 61     } 62     if(x<t[rt].val)insert(t[rt].l,x); 63     else insert(t[rt].r,x); 64     if(t[t[rt].l].sz/(double)t[rt].sz>0.666)flag=rt; 65     if(flag==t[rt].l || flag==t[rt].r)faf=rt; 66     pushup(rt); 67     return; 68 } 69 void del(int rt){ 70     if(!rt)return; 71     vt[++sz]=t[rt]; 72     st[++top]=rt; 73     del(t[rt].l); 74     del(t[rt].r); 75     return; 76 } 77 int pre(int rt,int x){ 78     int res=-2e9-1,pos=0; 79     while(rt){ 80         if(t[rt].val>=x){ 81             rt=t[rt].l; 82         } 83         else{ 84             if(t[rt].val>res){res=t[rt].val;pos=rt;} 85             rt=t[rt].r; 86         } 87     } 88     return pos; 89 } 90 int sub(int rt,int x){ 91     int res=2e9+1,pos=0; 92     while(rt){ 93         if(t[rt].val<=x){ 94             rt=t[rt].r; 95         } 96         else{ 97             if(t[rt].val<res){res=t[rt].val;pos=rt;} 98             rt=t[rt].l; 99         }100     }101     return pos;102 }103 int st2[mxn],top2=0,fafa;104 void Q_erase(int &rt,int x){105 //    if(!rt && x==299181)while(1);106     if(t[rt].val==x){107         t[rt].cnt--;108         t[rt].sz--;109         if(!t[rt].cnt){110             if(t[rt].l*t[rt].r==0){rt=t[rt].l+t[rt].r;return;}111             int p=t[rt].l;112             while(t[p].r){st2[++top2]=p;p=t[p].r;}113             if(top2){114                 t[st2[top2]].r=t[p].l;115                 pushup(st2[top2]);116                 t[p].l=t[rt].l;117                 t[p].r=t[rt].r;118                 while(top2)pushup(st2[top2--]);119             }120             else t[p].r=t[rt].r;121             if(fafa){122                 if(t[fafa].l==rt) t[fafa].l=p;123                 else t[fafa].r=p;124             }125             pushup(p);126             pushup(t[rt].l);127             rt=p;128         }129         pushup(fafa);130         return;131     }132     fafa=rt;133     if(x<t[rt].val)Q_erase(t[rt].l,x);134     else Q_erase(t[rt].r,x);135     pushup(rt);136     return;137 }138 int Q_rank(int rt,int x){139     int res=0;140     while(rt){141         if(t[rt].val<x){142             res+=t[t[rt].l].sz+t[rt].cnt;143             rt=t[rt].r;144         }145         else rt=t[rt].l;146     }147     return res+1;148 }149 int Q_num(int rt,int k){150     int res=0;151     while(rt){152         if(t[t[rt].l].sz>=k){153             res=t[rt].val;154             rt=t[rt].l;155         }156         else if(t[t[rt].l].sz+t[rt].cnt>=k)return t[rt].val;157             else k-=t[t[rt].l].sz+t[rt].cnt,rt=t[rt].r;158     }159     return res;160 }161 void Debug(int x){162     if(!x)return;163     printf("#%d: v:%d l:%d r:%d sz:%d cnt:%d\n",164         x,t[x].val,t[x].l,t[x].r,t[x].sz,t[x].cnt);165     Debug(t[x].l);Debug(t[x].r);166 }167 int n;168 int main(){169 //    freopen("in.txt","r",stdin);170 //    freopen("out.out","w",stdout);171     int i,j;172     n=read();173     int op,x;174     int tct=0;175     while(n--){176         op=read();x=read();177         if(op!=1)tct++;178         switch(op){179             case 1:{180                 flag=faf=0;sz=0;181                 insert(rot,x);182                 if(flag){183                     del(flag);184                     sort(vt+1,vt+sz+1);185                     if(flag==rot)Build(1,sz,rot);186                     else Build(1,sz,(t[faf].l==flag)?t[faf].l:t[faf].r);187                 }188                 break;189             }190             case 2:{fafa=0;Q_erase(rot,x);break;}191             case 3:{192                 int ans=Q_rank(rot,x);193                 printf("%d\n",ans);194                 break;195             }196             case 4:{197                 int ans=Q_num(rot,x);198                 printf("%d\n",ans);199                 break;200             }201             case 5:{202                 int res=pre(rot,x);203                 printf("%d\n",t[res].val);204                 break;205             }206             case 6:{207                 int res=sub(rot,x);208                 printf("%d\n",t[res].val);209                 break;210             }211             case 7:{212                 Debug(rot);213                 break;214             }215         }216     }217     return 0;218 }