【题意描述】
写一种数据结构，来维护一些数，其中需要提供以下操作： 
1. 插入x数 
2. 删除x数(若有多个相同的数，应只删除一个) 
3. 查询x数的排名(若有多个相同的数，应输出最小的排名) 
4. 查询排名为x的数 
5. 求x的前驱(前驱定义为小于x，且最大的数) 
6. 求x的后继(后继定义为大于x，且最小的数) 
【输入格式】
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6) 
（n < = 100000， 所有数字均在-10^7到10^7内 ）
【输出格式】
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input 
8
1 10
1 20
1 30
3 20
4 2
2 10
5 25
6 -1

Sample Output 
2
20
20
20

#include<cstdio>
#include<cstring>
using namespace std;
int root;
struct trnode
{
    int d,n,c,f,son[2];//d为值，f为父亲的编号，c为控制的节点个数，n为同值的节点个数
}tr[110000];int len;
 
void update(int x)//更新x所控制的节点数 
{
    int lc=tr[x].son[0],rc=tr[x].son[1];
    tr[x].c= tr[lc].c+ tr[rc].c+ tr[x].n;
}
void add(int d,int f)//添加值为d的点，认f为父亲，同时，f也认它为孩子
{
    len++;
    tr[len].d=d; tr[len].n=1;  tr[len].c=1;
    tr[len].f=f; if( d<tr[f].d) tr[f].son[0]=len; else tr[f].son[1]=len; 
    tr[len].son[0]=tr[len].son[1]=0;
}
 
void rotate(int x,int w)//左旋(x,0)或者右旋 (x,1)
{
    int f= tr[x].f,ff=tr[f].f;//x在旋转之前，要确定x的父亲f和爷爷ff 
    //下来建立关系 
    int r,R;//r表示儿辈，R表示父辈 
    //有四个角色：我x，我的儿子，我的父亲，我的爷爷 
    r=tr[x].son[w];R=f;//x的儿子 ->准备当新儿子 
    tr[R].son[1-w]=r ;
    if(r!=0) tr[r].f=R;
     
    r=x;R=ff;//x ->准备当新儿子
    if( tr[R] .son[0]==f) tr[R].son[0]=r;else  tr[R].son[1]=r;
    tr[r].f=R;
 
    r=f;R=x; //x的父亲 ->准备当新儿子
    tr[R].son[w]=r;
    tr[r].f=R;
     
    update(f); // 先更新处于下层的点f
    update(x); // 再更新上层的x
}
 
void splay(int x,int rt)// 该函数功能是为了让x成为rt的孩子（左或右都行）
{
    while(tr[x].f!=rt) // 如果rt是x的父亲，则什么都不用做，否则x就要不断向上旋转 
    {
        int f=tr[x].f,ff=tr[f].f; // 准备x的父亲和爷爷
        if( ff==rt) //如果 x的爷爷是rt，那么x只需要旋转一次（相当于跳一层）
        {
            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[1]==x){ rotate(f,0); rotate(x,0);}
            else if(tr[ff].son[0]==f && tr[f].son[1]==x){ rotate(x,0); rotate(x,1);}
            else if(tr[ff].son[1]==f && tr[f].son[0]==x){ rotate(x,1); rotate(x,0);}   
        }
    }
    if(rt==0) root=x;
}
int findip(int d)   //找值为d的节点的地址，补充：如果不存在d，有可能是接近d的（或大或小）
{
    int x=root;
    while(tr[x].d!=d)
    {
        if(d<tr[x].d)
        {
            if( tr[x].son[0]==0) break;
            else x=tr[x].son[0];
        }
        else // if( tr[x].d<d)
        {
            if( tr[x].son[1]==0) break;
            else x=tr[x].son[1];
        }
    }
    return x;
}
 
void ins(int d)//插入数值为d的一个节点
{
    if(root==0) { add(d,0); root=len; return ; }
     
    int x=findip(d);
    if( tr[x].d==d) 
    {
        tr[x].n++;
        update(x);
        splay(x,0);
    }
    else
    { 
        add(d,x);
        update(x);
        splay(len,0);
    }
}
 
void del(int d)   // 删除数值为d的一个节点
{
    int x=findip(d);splay(x,0);  //找人，并且让y 当树根
     
    if( tr[x].n>1) { tr[x].n--; update(x); return;}   // 多重身份，就不用删点
 
         if(tr[x].son[0]==0 && tr[x].son[1]==0){ root=0; len=0; }     // 四种情况
    else if(tr[x].son[0]==0 && tr[x].son[1]!=0){ root=tr[x].son[1]; tr[root].f=0; }
    else if(tr[x].son[0]!=0 && tr[x].son[1]==0){ root=tr[x].son[0]; tr[root].f=0;  }
    else //if( tr[x].son[0]!= 0&& tr[x].son[1]!=0)
    {
        int p=tr[x].son[0];while( tr[p].son[1]!=0) p= tr[p].son[1];splay(p,x);
         
        int r=tr[x].son[1],R=p;
         
        tr[R].son[1]=r ;
        tr[r].f= R;
         
        root=R;tr[root].f=0;
        update(R);
    }
}
int findpaiming(int d)//找排名 
{
    int x=findip(d);splay(x,0);
     
    return tr[tr[x].son[0]].c+1;
}
 
int  findshuzi(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 break;  //就是你
    }
    splay(x,0);
    return tr[x].d;
}
int findqianqu(int d) //找前驱
{
    int x= findip(d);splay(x,0);
    if( d<=tr[x].d && tr[x].son[0]!=0 )//如果是if( d<tr[x].d && tr[x].son[0]!=0 )则找到的是：小于等于d的前驱 
    {
        x=tr[x].son[0];
        while( tr[x].son[1]!=0) x= tr[x].son[1];
    }
    if( tr[x].d >=d) x=0;//如果是if( tr[x].d >d)则找到的是：小于等于d的前驱
    return x;
}
 
int findhouji(int d)  //找后继
{
    int x= findip(d);splay(x,0);
    if( tr[x].d<=d && tr[x].son[1]!=0 )
    {
        x=tr[x].son[1];
        while( tr[x].son[0]!=0) x= tr[x].son[0];
    }
    if( tr[x].d <=d) x=0;
    return x;
}
 
int main()
{
    //freopen("ptszs.in","r",stdin);
    //freopen("ptszs.out","w",stdout);
    int n;scanf("%d",&n);
    root=0;len=0;
    for(int i=1;i<=n;i++)
    {
        int cz,x;scanf("%d%d",&cz,&x);
             if(cz==1) ins(x);
        else if(cz==2) del(x);
        else if(cz==3) printf("%d\n",findpaiming(x) );
        else if(cz==4) printf("%d\n",findshuzi(x) );
        else if(cz==5) printf("%d\n",tr[findqianqu(x)].d);
        else if(cz==6) printf("%d\n",tr[findhouji(x)].d);
    }
    return 0;
}