题意

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)

\(n \leq 10^5\)

分析

平衡树板子题。

思维局限于split和merge，差点忘了求第k个怎么写了。直接迭代或者递归就好了。

时间复杂度\(O(n \log n)\)

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read()
{
    rg T data=0;
    rg int w=1;
    rg char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        data=data*10+ch-'0';
        ch=getchar();
    }
    return data*w;
}
template<class T>il T read(rg T&x)
{
    return x=read<T>();
}
typedef long long ll;

co int N=1e5+7;
int root;
int tot;
namespace T
{
    int siz[N],ch[N][2];
    int pri[N],val[N];
    
    int newnode(int v)
    {
        int x=++tot;
        siz[x]=1,ch[x][0]=ch[x][1]=0;
        pri[x]=rand(),val[x]=v;
        return x;
    }
    
    void pushup(int x)
    {
        siz[x]=siz[ch[x][0]]+1+siz[ch[x][1]];
    }
    
    void split(int x,int v,int&l,int&r)
    {
        if(!x)
        {
            l=r=0;
            return;
        }
        if(val[x]<=v)
        {
            l=x;
            split(ch[l][1],v,ch[l][1],r);
            pushup(l);
        }
        else
        {
            r=x;
            split(ch[r][0],v,l,ch[r][0]);
            pushup(r);
        }
    }
    
    int merge(int x,int y)
    {
        if(!x||!y)
            return x+y;
        if(pri[x]>pri[y])
        {
            ch[x][1]=merge(ch[x][1],y);
            pushup(x);
            return x;
        }
        else
        {
            ch[y][0]=merge(x,ch[y][0]);
            pushup(y);
            return y;
        }
    }
    
    void insert(int&t,int v)
    {
        int x,y;
        split(t,v,x,y);
        t=merge(x,merge(newnode(v),y));
    }
    
    void erase(int&t,int v)
    {
        int x,y,z;
        split(t,v-1,x,y);
        split(y,v,y,z);
        y=merge(ch[y][0],ch[y][1]);
        t=merge(x,merge(y,z));
    }
    
    int rank(int&t,int v)
    {
        int x,y;
        split(t,v-1,x,y);
        int res=siz[x]+1;
        t=merge(x,y);
        return res;
    }
    
    int kth(int&t,int k)
    {
        if(k==siz[ch[t][0]]+1)
            return val[t];
        if(k<=siz[ch[t][0]])
            return kth(ch[t][0],k);
        else
            return kth(ch[t][1],k-siz[ch[t][0]]-1);
    }
    
    int pre(int&t,int v)
    {
        int x,y;
        split(t,v-1,x,y);
        int res=kth(x,siz[x]);
        t=merge(x,y);
        return res;
    }
    
    int suc(int&t,int v)
    {
        int x,y;
        split(t,v,x,y);
        int res=kth(y,1);
        t=merge(x,y);
        return res;
    }
}
using namespace T;
using namespace std;

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    srand(20030506);
    int n;
    read(n);
    while(n--)
    {
        int opt,x;
        read(opt),read(x);
        if(opt==1)
            insert(root,x);
        else if(opt==2)
            erase(root,x);
        else if(opt==3)
            printf("%d\n",rank(root,x));
        else if(opt==4)
            printf("%d\n",kth(root,x));
        else if(opt==5)
            printf("%d\n",pre(root,x));
        else
            printf("%d\n",suc(root,x));
    }
    return 0;
}