没错这是神奇的平衡树（伸展树）QAQ

来自Daniel Sleator 和 Robert Endre Tarjan的神奇科技

先上板子哈 超详细的

题目为bzoj3224

传送门

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5+1e3+7;

int num[N];//标号为x的相等数字 有num个 
int sz[N];//此节点子树大小 
int rev[N];
int fa[N],son[N][2];//当前点父亲 左儿子0||右儿子1 
int rt;//根节点标号 
int key[N];//当前点数值 
int tot;//平衡树中节点数目 

void update(int x)
{
    sz[x]=sz[son[x][0]]+sz[son[x][1]]+num[x];
}//更新子树大小 （包括自己） 

void rotate(int x)
{
    int y=fa[x],z=fa[y],t=(son[y][0]==x);//相当于是y&x在旋 但这个过程y x要换父亲 因此要引入z t用来自适应 
    if(z)//非根节点 
        son[z][son[z][1]==y]=x;//将z的某一个儿子设为x 
    fa[x]=z;//连上 
    son[y][!t]=son[x][t];//相连最近儿子（左儿或右儿） 
    fa[son[x][t]]=y;
    son[x][t]=y;//将y连到x下 
    fa[y]=x;
    update(y);//更新子树大小 
    update(x);
}

void splay(int x,int s)//当前节点  旋到何处结束 
{
    while(fa[x]!=s)//即旋到x连到s下结束 
    {
        int y=fa[x],z=fa[y];//z为x的爷爷 y的父亲 
        if(z!=s)//控制边界 
        {//保证平衡树平衡 
            if((son[y][0]==x)^(son[z][0]==y))//x，y，z不在一条链上 
                rotate(x);//正常操作 
            else//否则折叠这个长链 
                rotate(y);
        }
        rotate(x);//双旋 上边的操作并未将当前点继续上传 因此要再转一下 
    }
    if(!s)//换根 即旋转到根结束 
        rt=x;
}

void insert(int &x,int s,int v)//插入：标号 祖先 数值 
{
    if(!x)//为虚根节点 并且根节点只有一个 
    {
        x=++tot;//记录标号 
        fa[x]=s;//连到s下 
        key[x]=v;//保存这个数
        sz[x]=num[x]=1;//子树大小和数据数都为1 
        son[x][0]=son[x][1]=0;//建上空的叶子节点 
        splay(x,0);//旋转至根节点 
        return;
    }
    if(num[x]>1)//此点数据数大于1 及是否存在 
    {
        sz[x]++;
        num[x]++;//子树大小和此点数据数都增加 
        splay(x,0);//旋转至根节点 
        return;
    }
    insert(son[x][v>key[x]],x,v);//如果前两个条件都不满足 则把它连上它的父亲 递归 
    update(x);//及时更新子树大小 
}

int get(int v)//找到数值为v的树上结点标号 
{
    int x=rt;
    while(key[x]!=v&&x)//从根开始 
        x=son[x][v>key[x]];//通过逼近 找到比v小的（即v的左右儿子）其父亲即为所求 
    return x;
}

void del(int x)//删除某一值 
{
    x=get(x);
    if(!x)
        return;
    splay(x,0);//旋转至根节点 
    if(num[x]>1)
    {
        num[x]--;
        sz[x]--;
        return;
    }//如果有很多 删去其中一个 并将num和sz更新 
    if(!son[x][0]||!son[x][1])//左右儿子其中一个不存在 
        rt=son[x][0]+son[x][1];//直接搞啊 反正一个是0 加上也无妨 
    else
    {
        int y=son[x][1];//右儿子 
        while(son[y][0])//如果有左儿子 
            y=son[y][0];//就一直向下 找到第一个比x大的数值所在节点 
        splay(y,x);//然后把y旋转至x 
        son[y][0]=son[x][0];//把x的左儿子给y 
        fa[son[x][0]]=y;//同上 
        rt=y;//把根搞成y 
    }
    update(rt);//正经换根操作 
    fa[rt]=0;//同上 
}

int rank(int v)//找到数值为v的节点的排名 
{
    int x=rt,ret=0;//此时先从根找 ret维护答案 
    while(x)//非虚根 
    {
        if(v<=key[x])//如果此数值≤当前数值 那么将x变成它的左儿子 即向左搜 
            x=son[x][0];
        else
        {
            ret+=sz[son[x][0]]+num[x];//排名即为左儿子子树大小和左儿子的大小之和 
            x=son[x][1];//然后把它变成自己的右儿子 即向右搜 
        } 

    }
    return ret+1;//加上自己 
}

int kth(int v)//查询排名为v的数 
{
    int x=rt;
    while(v<=sz[son[x][0]]||v>sz[son[x][0]]+num[x])
    {
        if(v<=sz[son[x][0]])
            x=son[x][0];
        else//若大于 则减一下 然后把x移到左儿子处 
            v-=sz[son[x][0]]+num[x],x=son[x][1];
    }
    return key[x];
}

int pre(int v)//前驱 第一个比v小的数值所在节点的数值 
{
    int x=rt,ret=-0x7fffffff;//查询最小 因此此处赋值为负无穷 
    while(x)
    {
        if(v>key[x])
            ret=max(ret,key[x]),x=son[x][1];//因为要在左子树一直向右下走 所以要取max 
        else
            x=son[x][0];//否则自然要向左走 
    }
    return ret;
}

int suf(int v)//后继 第一个比v大的数值所在节点的数值 
{
    int x=rt,ret=0x7fffffff;//查询最大 因此此处赋值为正无穷 
    while(x)
    {
        if(v<key[x])
            ret=min(ret,key[x]),x=son[x][0];//因为要在右子树一直向左下走 所以要取min 
        else
            x=son[x][1];//否则自然要向右走 
    } 
    return ret;
}

int n;

int main()
{
    scanf("%d",&n);
    while(n--)
    {
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1)
            insert(rt,0,x);//加入 
        if(op==2)
            del(x);//删除 
        if(op==3)
            printf("%d\n",rank(x));
        if(op==4)
            printf("%d\n",kth(x));
        if(op==5)
            printf("%d\n",pre(x));
        if(op==6)
            printf("%d\n",suf(x));
    }
}

讲解待补