Splay

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10,INF=1e9;
struct
{
    int ff;//结点的父亲
    int ch[2];//结点的左右儿子   0左1右
    int val;//结点的值
    int cnt,size;//结点的数量，和子树规模
}tr[N];
int root,idx;

void pushup(int p)//更新p的规模
{
    tr[p].size=tr[tr[p].ch[0]].size+tr[tr[p].ch[1]].size+tr[p].cnt;
}
void zig_zag(int x)
{
    int y=tr[x].ff;//x的父亲是y
    int z=tr[y].ff;//y的父亲是z，即x的祖父
    int k=(tr[y].ch[1]==x);//验证x是y的左儿子还是右儿子  0左1右
    tr[z].ch[tr[z].ch[1]==y]=x;//y在z的子树位置转成x  Z的原来的Y的位置变为X
    tr[x].ff=z;//x父亲变成z
    tr[y].ch[k]=tr[x].ch[k^1];//X的与X原来在Y的相对的那个儿子变成Y的儿子
    tr[tr[x].ch[k^1]].ff=y;//更新父节点
    tr[x].ch[k^1]=y;//X的 与X原来相对位置的儿子变成 Y
    tr[y].ff=x;//更新父节点
    pushup(y),pushup(x);//先y后x
}

void splay(int x,int goal)//将x旋转为goal的儿子，如果goal是0则旋转到根
{
    while(tr[x].ff!=goal)//当x的父亲不是goal。说明需要上升高度
    {
        int y=tr[x].ff,z=tr[y].ff;
        if(z!=goal)//如果z不是goal，则至少两次旋转
        {
           (tr[z].ch[0]==y)^(tr[y].ch[0]==x)?zig_zag(x):zig_zag(y);//共线先转y，不共线先转x
        }
        zig_zag(x);//无论共不共线，x最后都要悬一次。以及z是目标的话，则只需要转一次x就行，即高度上升1
    }
    if(goal==0)root=x;//如果goal是0，则将根节点更新为x
}

inline void find(int x)//查找x的位置，并将其旋转到根节点
{
    int u=root;//令u是根
    if(!u)return;//树空
    while(tr[u].ch[x>tr[u].val]&&x!=tr[u].val)//当存在儿子并且当前位置的值不等于x
        u=tr[u].ch[x>tr[u].val];//跳转到儿子，查找x的父节点
    splay(u,0);//把当前位置旋转到根节点
}
inline void insert(int x)//插入x
{
    int u=root,ff=0;//当前位置u，u的父节点ff
    while(u&&tr[u].val!=x)//当u存在并且没有移动到当前的值
    {
        ff=u;//向下u的儿子，父节点变为u
        u=tr[u].ch[x>tr[u].val];//大于当前位置则向右找，否则向左找
    }
    if(u)//存在这个值的位置
        tr[u].cnt++;//增加一个数
    else//不存在这个数字，要新建一个节点来存放
    {
        u=++idx;//新节点的位置
        if(ff)//如果父节点非根
            tr[ff].ch[x>tr[ff].val]=u;
        tr[u].ch[0]=tr[u].ch[1]=0;//不存在儿子
        tr[idx].ff=ff;//父节点
        tr[idx].val=x;//值
        tr[idx].cnt=1;//数量
        tr[idx].size=1;//大小
    }
    splay(u,0);//把当前位置移到根，保证结构的平衡
}
inline int Next(int x,int f)//查找x的前驱(0)或者后继(1)
{
    find(x);
    int u=root;//根节点，此时x的父节点（存在的话）就是根节点
    if(tr[u].val>x&&f)return u;//如果当前节点的值大于x并且要查找的是后继
    if(tr[u].val<x&&!f)return u;//如果当前节点的值小于x并且要查找的是前驱
    u=tr[u].ch[f];//查找后继的话在右儿子上找，前驱在左儿子上找
    while(tr[u].ch[f^1])u=tr[u].ch[f^1];//要反着跳转，否则会越来越大（越来越小）
    return u;//返回位置
}

inline void Delete(int x)//删除x
{
    int last=Next(x,0);//查找x的前驱
    int next=Next(x,1);//查找x的后继
    splay(last,0);splay(next,last);
    //将前驱旋转到根节点，后继旋转到根节点下面
    //很明显，此时后继是前驱的右儿子，x是后继的左儿子，并且x是叶子节点
    int del=tr[next].ch[0];//后继的左儿子
    if(tr[del].cnt>1)//如果超过一个
    {
        tr[del].cnt--;//直接减少一个
        splay(del,0);//旋转
    }
    else
        tr[next].ch[0]=0;//这个节点直接丢掉（不存在了）
}


inline int kth(int x)//查找排名为x的数
{
    int u=root;//当前根节点
    if(tr[u].size<x)//如果当前树上没有这么多数
        return 0;//不存在
    while(1)
    {
        int y=tr[u].ch[0];//左儿子
        if(x>tr[y].size+tr[u].cnt)
        //如果排名比左儿子的大小和当前节点的数量要大
        {
            x-=tr[y].size+tr[u].cnt;//数量减少
            u=tr[u].ch[1];//那么当前排名的数一定在右儿子上找
        }
        else//否则的话在当前节点或者左儿子上查找
            if(tr[y].size>=x)//左儿子的节点数足够
                u=y;//在左儿子上继续找
            else//否则就是在当前根节点上
                return tr[u].val;
    }
}


int main()
{
    int n;
    cin>>n;
    insert(1e9);
    insert(-1e9);
    while(n--)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1)
        {
            insert(x);
        }
        else if(opt==2)
        {
            Delete(x);
        }
        else if(opt==3)
        {
             find(x);
            printf("%d\n",tr[tr[root].ch[0]].size);
        }
        else if(opt==4)
        {
            printf("%d\n",kth(x+1));
        }
        else if(opt==5)
        {
            printf("%d\n",tr[Next(x,0)].val);
        }
        else if(opt==6)
        {

            printf("%d\n",tr[Next(x,1)].val);
        }
    }
    return 0;
}

Treap

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10,INF=1e8; 
int n;
struct{
  int l,r;//左右子树
  int key,val;
  int cnt,size;//数出现的次数、子树的规模
}tr[N];
int root,idx;//根节点，目前能分配的tr数组的下标

void pushup(int p)//用子节点计算父节点信息
{
    tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;//计算p树的规模，是左右子树的规模和p结点值key的个数之和
}
int new_node(int key)//为key值分配一个新节点
{
    tr[++idx].key=key;//key赋值
    tr[idx].val=rand();//val随机
    tr[idx].cnt=1,tr[idx].size=1;//新结点cnt是1，子树规模是1
    return idx;//返回分配的下标
}
void build()
{
    new_node(-INF),new_node(INF);//为了避免越界，避免边界情况的特殊判断，所以插入正无穷和负无穷结点
    //仅由这两个结点构成的BST就是一棵初始的空BST.idx分别是1和2
    root=1,tr[1].r=2;
    pushup(root);//更新一下root（父节点）信息
}
void zig(int &p)//引用p，可改变p   右旋
{
    int q=tr[p].l;//看图写代码
    //q的右子树给p当左子树  p给q当右子树  p变成q
    tr[p].l=tr[q].r,tr[q].r=p,p=q;
    pushup(tr[p].r),pushup(p);//调整p的右子树和p的规模size
}
void zag(int &p)//引用p，可改变p   左旋
{
    int q=tr[p].r;//看图写代码
    //q的左子树给p当右子树  p给q当左子树  p变成q
    tr[p].r=tr[q].l,tr[q].l=p;p=q;
    pushup(tr[p].l),pushup(p);//调整p的右子树和p的规模size
}

void insert(int &p,int key)
{
    if(!p)p=new_node(key);//p不存在的话（为空），产生一个节点
    else if(tr[p].key==key)tr[p].cnt++;//如果已经有了key的话，cnt加一
    else if(tr[p].key>key)//如果小于该节点，则进入该节点左子树
    {
         insert(tr[p].l,key);//插入左子树
         if(tr[tr[p].l].val>tr[p].val)zig(p);//如果左子树的val值大于根的val，要右旋
    }
    else if(tr[p].key<key)//如果key大于该节点，则进入该节点右子树
    {
         insert(tr[p].r,key);//插入右子树
         if(tr[tr[p].r].val>tr[p].val)zag(p);//如果右子树的val值大于根的val，要左旋
    }
    pushup(p);//调整p的规模
}
void remove(int &p,int key)//删除p
{
    if(!p)return;//如果p不存在，就返回
    if(tr[p].key==key)////结点与key相同
    {
        if(tr[p].cnt>1)tr[p].cnt--;//如果key值有多个，则减一个
        else if(tr[p].l||tr[p].r)//如果左右结点存在一个或两个
        {
            if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)//如果右子树不存在或者如果左子树值比右子树大
            {
                zig(p);//右旋
                remove(tr[p].r,key);//之后删除右子树即已成为叶子
            }
            else //如果右子树不存在或者如果左节点值比右节点小
            {
                zag(p);//左旋
                remove(tr[p].l,key);//删除左子树即已成为叶子
            }
        }
        else p=0;//没有子树即就是叶子
    }
    else if(tr[p].key>key)remove(tr[p].l,key);//如果父节点大于该值，则进入左子树继续删除
    else remove(tr[p].r,key);//如果父节点小于该值，则进入右子树继续删除
    pushup(p);//更新p的size
}

int get_rank_by_key(int p,int key)//通过数值找排名
{
    if(!p)return 0;//如果p值不存在
    if(tr[p].key==key)return tr[tr[p].l].size+1; //找到该结点后，排名就是左子树的规模加上1
    if(tr[p].key>key)return get_rank_by_key(tr[p].l,key);//如果该结点值大于key，排名得进入左子树查
    if(tr[p].key<key)return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);////如果该节点值小于key，进入右子树查rank
}
int get_key_by_rank(int p,int rank)//通过排名找数值
{
    if(!p)return INF;//如果p值不存在
    if(tr[tr[p].l].size>=rank)return get_key_by_rank(tr[p].l,rank);//左子树规模size大于rank,进入左子树
    if(tr[tr[p].l].size+tr[p].cnt>=rank)return tr[p].key;//rank小于等于左子树size和cnt之和
    if(tr[tr[p].l].size+tr[p].cnt<rank)return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
    //左子树size和该节点值cnt小于rank，就是rank在右子树中，找到数值
}
int get_pre_by_key(int p,int key)//找出小于key的最大值
{
    if(!p)return -INF;//如果p值不存在
    if(tr[p].key>=key)return get_pre_by_key(tr[p].l,key);//结点p的key大于等于key，找前驱就进入左子树找
    if(tr[p].key<key)return max(tr[p].key,get_pre_by_key(tr[p].r,key));//结点p的key小于key，找前驱就在右子树或结点p中最大值
}
int get_next_by_key(int p,int key)//找出大于key的最小值
{
    if(!p)return +INF;//如果p值不存在
    if(tr[p].key<=key)return get_next_by_key(tr[p].r,key);//结点p的key小于等于key，找后继就在右子树中
    if(tr[p].key>key)return min(tr[p].key,get_next_by_key(tr[p].l,key));//结点p的key大于key，找后继就在左子树和该节点中的最小值
}
int main()
{
    cin>>n;
    int opt,x;int t;
    build();
    while(n--)
    {
      scanf("%d%d",&opt,&x);
      if(opt==1){
          insert(root,x);//从root插入x
      }
      else if(opt==2)
      {
          remove(root,x);//从root开始检索x，并删除它
      }
      else if(opt==3)
      {
           t=get_rank_by_key(root,x);//从值得到排序
           printf("%d\n",t-1);//减一，因为负哨兵
      }
      else if(opt==4)
      {
          t=get_key_by_rank(root,x+1);//从排序得到值，因为负哨兵，所以加1
          printf("%d\n",t);

      }
      else if(opt==5)
      {
          t=get_pre_by_key(root,x);//找到前驱
          printf("%d\n",t);
      }
      else if(opt==6)
      {
          t=get_next_by_key(root,x);//找后继
          printf("%d\n",t);
      }
    }
    return 0;
}