伸展树Splay做法:

#include<bits/stdc++.h>
#define lc(x) tr[x].ch[0]
#define rc(x) tr[x].ch[1]
#define fa(x) tr[x].fa
using namespace std;
const int N = 2e6 + 10;
int id, rt;
struct node{int fa, val, cnt, siz, ch[2];}tr[N];

bool dir(int x)//判断x是左孩子还是右孩子
{return x == tr[fa(x)].ch[1];}

void pushup(int x)//更新x的子树大小siz
{tr[x].siz = tr[lc(x)].siz + tr[rc(x)].siz + tr[x].cnt;}

void rotate(int x)//关于x与y之间的边旋转
{
    int y = fa(x), z = fa(y);
    bool dx = dir(x), dy = dir(y);//d:direction x是左还是右
    tr[y].ch[dx] = tr[x].ch[!dx];//x将靠近y一侧给y
    tr[x].ch[!dx] = y;//y成为x的儿子
    if (z) tr[z].ch[dy] = x;//x替代y，成为z的儿子
    if (tr[y].ch[dx]) fa(tr[y].ch[dx]) = y;//y拿走x一个儿子
    fa(y) = x; fa(x) = z; //更新父亲
    pushup(y); pushup(x);//更新siz
}

void splay(int &z, int x)//将x上移至根节点z
{
    int xfa = fa(x), zfa = fa(z);
    while (xfa != zfa)
    {
        if (fa(xfa) != zfa)
        {
            //通过zig-zig和zig-zag两种操作维护树的平衡性
            if (dir(x) == dir(xfa)) rotate(xfa);//zig-zig
            else rotate(x);//zig-zag
        }
        rotate(x);
        xfa = fa(x);
    }
    z = x;//修改树根 
}

void find(int &z, int v)//在z子树中按照查找值为v的元素
{   
    int x = z, y = fa(x);
    while (x and tr[x].val != v)
    {
        y = x;
        if (v < tr[x].val) x = lc(y);//向左找
        else x = rc(y);//向右找
    }
    splay(z, (x ? x : y));//上移至根节点
}

void loc(int &z, int k)//在z的子树中按查找排名k的元素
{
    int x = z;
    while (true)
    {
        if (tr[lc(x)].siz >= k) x = lc(x);//向左找
        else if (tr[lc(x)].siz + tr[x].cnt >= k) break;//答案为x
        else
        {
            k -= tr[lc(x)].siz + tr[x].cnt;
            x = rc(x);//向右找
        }
    }
    splay(z, x);//上移至根节点
}

/*注意：merge函数默认x中元素均小于y中元素*/
/*所以从一颗平衡树中分裂出来的两颗平衡树可以合并*/
int merge(int x, int y)//合并以x与y为根的子树，返回新的树根
{
    if (!x or !y) return x + y;
    loc(y, 1);//找到y中最小值，此时y子树根节点的左子树一定为空
    lc(y) = x;//x成为y的左儿子
    fa(x) = y;//y成为x的父亲
    pushup(y);
    return y;
}

void insert(int v)//插入值为v的元素
{
    int x = rt, y = 0;
    while (x and tr[x].val != v)//按值查找至合适位置
    {
        y = x;
        if (v <= tr[x].val) x = lc(y);//向左找
        else x = rc(y);//向右找
    }
    if (x) {tr[x].cnt ++; tr[x].siz ++; }//存在该节点就直接增加cnt
    else
    {
        //新建值为x的节点
        x = ++ id;
        tr[x] = node{y, v, 1, 1, {0, 0}};
        //struct node{int fa, val, cnt, siz, ch[2];}
        if (y)
        {
            if (v < tr[y].val) lc(y) = x;//成为左孩子
            else rc(y) = x;//成为右孩子
        }
    }
    splay(rt, x);//上移至根节点
}

bool remove(int v)//删除值为v的节点，返回是否删除成功
{
    find(rt, v);//按值查找值为v的节点，上移至根节点
    if (!rt or tr[rt].val != v) return false;//没有值为v的节点，删除失败
    tr[rt].cnt --; tr[rt].siz --;
    if (!tr[rt].cnt)//如果根节点删没了
    {
        int x = lc(rt), y = rc(rt);
        fa(x) = fa(y) = 0;//原本的左右孩子独立成树
        //应为x与y分别是原树根的左右孩子，所以x中元素均小于y中元素
        rt = merge(x, y);//合并左右孩子
    }
    return true;//删除成功
}

int get_rank(int v)//查询值为v元素在树中能排第几
{
    find(rt, v);//将值为v的元素上移至根节点
    if (tr[rt].val < v) return tr[lc(rt)].siz + tr[rt].cnt + 1;
    else return tr[lc(rt)].siz + 1;
}


int get_kth(int k)//查询第k大元素的值
{
    if (k > tr[rt].siz) return -1;//越界
    loc(rt, k);//查询元素，移动到根节点
    return tr[rt].val;
}

int get_prev(int v)//查询值为v元素的前驱
{
    find(rt, v);//找到元素并伸展至根结点，其前驱即为左子树中最大元素
    if (rt and tr[rt].val < v)
        return tr[rt].val;//不存在值为v元素，树根值小于v，即为答案
    int x = lc(rt);//进入左子树
    if (!x) return -1;//没有左子树，v即为最小元素，没有前驱
    while (rc(x)) x = rc(x);//一直走到没有右孩子，得到最大值
    splay(rt, x);//将答案上移至根节点
    return tr[rt].val;
}

int get_next(int v)//查询值为v元素的后继
{
    find(rt, v); //找到元素并伸展至根结点，其前驱即为右子树中最小元素
    if (rt and tr[rt].val > v)
        return tr[rt].val;//不存在值为v元素，树根值大于v，即为答案
    int x = rc(rt);//进入右子树
    if (!x) return -1;//没有右子树，v即为最大元素，没有后继
    while (lc(x)) x = lc(x);//一直走到没有左孩子，得到最小值
    splay(rt, x);//将答案上移至根节点
    return tr[rt].val;
}

int main()//完结撒花🎉
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int op, x; cin >> op >> x;
        if (op == 1) insert(x);
        else if (op == 2) remove(x);
        else if (op == 3) cout << get_rank(x) << endl;
        else if (op == 4) cout << get_kth(x) << endl;
        else if (op == 5) cout << get_prev(x) << endl;
        else if (op == 6) cout << get_next(x) << endl;
    }
    return 0;
}

C05【模板】FHQ Treap P3369 普通平衡树

#include<bits/stdc++.h>
using namespace std;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
const int N=1e5+10;
struct node{int ls,rs,val,siz,rnd;}tr[N]; int rt,trlen;
int newd(int v){ tr[++trlen]={0,0,v,1,rand()};return trlen; }
void pushup(int p){ tr[p].siz=tr[lc(p)].siz+tr[rc(p)].siz+1; }
void split(int p,int v,int &x,int &y)//得到相互独立两棵树，x和y为根，x子树所有节点val值<=v，y子树所有节点val>v
{
    if(p==0){x=y=0;return;}
    if(tr[p].val<=v)
    {
        x=p;
        split(rc(p),v,rc(x),y);
    }
    else
    {
        y=p;
        split(lc(p),v,x,lc(y));
    }
    pushup(p);
}
int merge(int x,int y)//合并以x和y为根的两棵子树
{
    if( !x || !y )return x+y;
    if(tr[x].rnd<tr[y].rnd)
    {
        rc(x)=merge(rc(x),y);
        pushup(x);
        return x;
    }
    else
    {
        lc(y)=merge(x,lc(y));
        pushup(y);
        return y;
    }
}
void ins(int v)
{
    int x,y,z;
    split(rt,v,x,y);
    rt=merge(merge(x,newd(v)),y);
}
void del(int v)
{
    int x,y,z;
    split(rt,v-1,x,y);
    split(y,v,y,z);
    rt=merge(merge(x,merge(lc(y),rc(y))),z);
}
int getrnk(int v)
{
    int x,y;
    split(rt,v-1,x,y);
    int res=tr[x].siz+1;
    rt=merge(x,y);
    return res;
}
int getval(int p,int k)
{
    if(k==tr[lc(p)].siz+1)return tr[p].val;
    if(k<=tr[lc(p)].siz)  return getval(lc(p),k);
    else                  return getval(rc(p),k-tr[lc(p)].siz-1);
}
int getpre(int v)
{
    int x,y;
    split(rt,v-1,x,y);
    int k=tr[x].siz;
    int res=getval(x,k);
    rt=merge(x,y);
    return res;
}
int getnxt(int v)
{
    int x,y;
    split(rt,v,x,y);
    int res=getval(y,1);
    rt=merge(x,y);
    return res;
}
int main()
{
    int n;scanf("%d",&n);
    rt=trlen=0;
    for(int i=1,op,v;i<=n;++i)
    {
        scanf("%d%d",&op,&v);
        if(op==1)ins(v);
        else if(op==2)del(v);
        else if(op==3)printf("%d\n",getrnk(v));
        else if(op==4)printf("%d\n",getval(rt,v));
        else if(op==5)printf("%d\n",getpre(v));
        else if(op==6)printf("%d\n",getnxt(v));   
    }
    return 0;
}