点个赞

#include<iostream>
#include<cstring>
#include<random>
#include<algorithm>
using namespace std;
const int N=1e5+10;
std::mt19937 rnd(233);  //高性能的随机函数   种子取233
struct Node{
    int l,r;    //左孩子节点的编号  右孩子节点的编号 编号其实就是下标
    int val;    //该节点内的权值
    int key;    //该节点的随机索引 即随机优先级
    int size;   //以该节点为根的所形成的树的大小
}tr[N];
//idx给每个节点分配的编号(下标) 最后它记录的就是这棵树中节点的总个数
//root记录的就是这棵树的根节点
int idx,root;
//x树  y树  z树   后面的操作需要用到  先定义为全局变量
int x,y,z;

//建立新节点  给该节点分配编号 同记录信息
inline int newnode(int val)
{
    tr[++idx].val=val;  //记录该节点的值为val
    tr[idx].key=rnd();  //随机生成该节点的优先级
    tr[idx].size=1;     //以该节点为根的树的大小为1
    return idx;         //返回分配给该节点的编号idx
}

//更新节点的信息  记录以该节点u为根的树的大小
inline void update(int u)
{
    tr[u].size=tr[tr[u].l].size+tr[tr[u].r].size+1;
}

//分裂操作:按val值将u树分裂成x树和y树
//这里用 引用 将分裂得到的x树和y树 返回回去
void split(int u,int val,int &x,int &y)
{
    //如果要分裂的当前这棵u树是不存在的 那么不可能分裂出x树和y树
    //所以把x和y都设为0
    if(!u)
        x=y=0;
    else
    {
        //如果当前节点的值<=val 根据二叉搜索树的性质 该节点的左子树肯定都<=val
        //但是当前节点的右子树中存在大于val的节点  因此我们需要对右子树再进行递归分裂
        if(tr[u].val<=val)
        {
            x=u;
            //按val值将tr[u].r右子树分裂成 tr[u].r树 和y树
            split(tr[u].r,val,tr[u].r,y);
        }
        else
        {
            y=u;
            //按val值将tr[u].l左子树分裂成x树和tr[u].l树
            split(tr[u].l,val,x,tr[u].l);
        }
        //分裂完了之后 要记得更新节点信息
        update(u);
    }
}

//将x树和y树合并 返回的结果是这两棵树合并后的那个根节点
int merge(int x,int y)
{
    //如果x树不存在y树存在 那么合并后就只有y树 因此返回y树
    //如果y树不存在x树存在 那么合并后就只有x树 因此返回x树
    if(!x||!y)
        return x+y;
    //这里当作是大根堆来处理 写成> 或者>=都可以
    //也可以当作小根堆来处理 即写成< <= 那么就是小根堆
    if(tr[x].key>tr[y].key)
    {
        //根据二叉堆的大根堆性质tr[x].key>tr[y].key 那么x在y的上方
        //根据二叉搜索树的性质,我们必须保证x树中的值<=y树中的值 所以y树在右子树
        //综上 y树是x的右子树 因此我们把y树和x原来的右子树合并 形成 x树新的右子树
        tr[x].r=merge(tr[x].r,y);
        //更新以x为根的树的大小信息
        update(x);
        //将y树合并到x树 合并后根节点就是x
        return x;
    }
    else
    {
        //根据二叉堆的大根堆性质tr[y].key>tr[x].key 那么y在x的上方
        //根据二叉搜索树的性质,我们必须保证x树中的值<=y树中的值 所以x树在左子树
        //综上 x树是y的左子树 因此我们把x树和y原来的左子树合并 形成 y树新的左子树
        tr[y].l=merge(x,tr[y].l);
        //更新以y为根的树的大小信息
        update(y);
        //将x树合并到y树 合并后根节点就是y
        return y;
    }
}

//插入
void insert(int val)
{
    //先按值val分裂成x树和y树
    split(root,val,x,y);
    //然后新生成节点newnode(val) 把这个节点和x树合并 得到一棵树
    //我们再将这棵树和y树合并  就得到了插入val后的完整的新树
    root=merge(merge(x, newnode(val)),y);
}

//删除
void del(int val)
{
    //第一步:按值val将root树分裂成x树和z树 分裂完了之后x树都是<=val z树都是>val
    split(root,val,x,z);
    //第二步:按值val-1将x树分裂成x树和y树 分裂完了之后x树都是<=val-1 y树都是>val-1 也就是说y树都是=val
    split(x,val-1,x,y);
    //第三步:将y的左子树和右子树合并 它俩众叛亲离偷偷合并抛弃了父节点y 那么就相当于删除了y这个根
    //然后我们把它俩合并后得到的新树的根节点赋值给y
    y=merge(tr[y].l,tr[y].r);
    //第四步:将x树和 合并后得到的新树y合并 又得到一个新树
    //第五步:再将这棵新树和z树合并 最终得到将val删除后的新树
    root=merge(merge(x,y),z);
}

//查询val值的排名
void getrank(int val)
{
    //按值val-1将root树分裂成x树和y树 那么此时x树中节点值都是<=val-1的
    split(root,val-1,x,y);
    //统计一下x树中的大小(即可知道有多少个数比val小)
    // 有tr[x].size个数比val小,然后再+1 那么就是val值的排名了
    printf("%d\n",tr[x].size+1);
    //有分裂一定有合并 分离完了要记得合并回去
    root=merge(x,y);
}

//查询排名为rank对应的大数
void getnum(int rank)
{
    int u=root;
    while(u)
    {
        if(tr[tr[u].l].size+1==rank)    //找到排名为rank所对应的数 就可以退出了
            break;
        else if(tr[tr[u].l].size>=rank) //在左子树中
            u=tr[u].l;
        else    //在右子树中
        {
            rank-=tr[tr[u].l].size+1;
            u=tr[u].r;
        }
    }
    printf("%d\n",tr[u].val);
}

//寻找前驱
void pre(int val)
{
    //按值val-1将root数分裂成x树(左子树)和y树(右子树)
    split(root,val-1,x,y);
    int u=x;
    //找到x树中的最右节点 则它就是val的前驱
    while(tr[u].r)
        u=tr[u].r;
    printf("%d\n",tr[u].val);
    //有分裂一定有合并 分离完了要记得合并回去
    root=merge(x,y);
}

//寻找后继
void nxt(int val)
{
    //按值val将root数分裂成x树(左子树)和y树(右子树)
    split(root,val,x,y);
    int u=y;
    //找到y树中的最左节点 则它就是val的后继
    while(tr[u].l)
        u=tr[u].l;
    printf("%d\n",tr[u].val);
    //有分裂一定有合并 分离完了要记得合并回去
    root=merge(x,y);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1)   //插入
            insert(x);
        else if(op==2)  //删除
            del(x);
        else if(op==3)  //求排名
            getrank(x);
        else if(op==4)  //求第rank对应的数
            getnum(x);
        else if(op==5)  //求数x的前驱
            pre(x);
        else if(op==6)  //求数x的后继
            nxt(x);
    }
    return 0;
}