具体讲解见OI-wiki（他的左旋右旋跟蓝书的有点不一样，按照蓝书的理解，代码见下），下面是一些补充
拓展：
1.将一个序列插入到\(x\)的后面：找到\(x\)的后继\(y\)，先将\(x\)伸展到根，再将\(y\)伸展到\(x\)的右子树，此时由于\(y\)是\(x\)的后继所以\(y\)的左儿子为空；对序列建出一棵二叉树（可以像线段树那个样子建，也可以直接建成一条链，反正是二叉树就可以了，但是要保证中序遍历），令\(y\)的左儿子为这棵Splay树的根节点即可
2.将一个序列删除：设删除序列为\([l,r]\)，则将\(l-1\)伸展到根节点，再将\(r+1\)伸展到根节点的右儿子，令\(r+1\)的左儿子为空即可
代码见下
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100010;
struct treap
{
int l,r;
int cnt,Size;
int val;
}a[N];
int tot,n,INF=0x7fffffff,root,fa[N];
int New(int val)
{
a[++tot].val=val;
a[tot].cnt=a[tot].Size=1;
return tot;
}
void update(int p)
{
a[p].Size=a[a[p].l].Size+a[a[p].r].Size+a[p].cnt;
}
void build()
{
New(INF),New(-INF);
a[1].l=2,fa[2]=1;//记录每个点的父亲，这样方便splay操作
root=1;
update(1);
}
pair<int,int> getrank(int p,int val)//first是答案rank，second是得到答案的点，最后会进行splay
{
if(!p) return make_pair(0,-1);//-1表示没找到，不进行splay
if(val==a[p].val) return make_pair(a[a[p].l].Size,p);
pair<int,int> res;
if(val<a[p].val) return getrank(a[p].l,val);
res=getrank(a[p].r,val);
return make_pair(a[a[p].l].Size+a[p].cnt+res.first,res.second);
}
pair<int,int> getval(int p,int rank)//first是答案val，second是得到答案的点，最后会进行splay
{
if(rank<=a[a[p].l].Size) return getval(a[p].l,rank);
if(rank<=a[a[p].l].Size+a[p].cnt) return make_pair(a[p].val,p);
return getval(a[p].r,rank-(a[a[p].l].Size+a[p].cnt));
}
int get(int x)//判断x是其父亲的左儿子还是右儿子
{
if(a[fa[x]].l==x) return 0;//左儿子
else return 1;//右儿子
}
void zig(int p)//右旋（注意这里没有引用了）
{
int q=a[p].l,flag=get(p);
a[p].l=a[q].r;
if(a[q].r) fa[a[q].r]=p;
a[q].r=p,fa[q]=fa[p],fa[p]=q;
if(fa[q])
{
if(!flag) a[fa[q]].l=q;
else a[fa[q]].r=q;
}
update(p),update(q);
}
void zag(int p)//左旋
{
int q=a[p].r,flag=get(p);
a[p].r=a[q].l;
if(a[q].l) fa[a[q].l]=p;
a[q].l=p,fa[q]=fa[p],fa[p]=q;
if(fa[q])
{
if(!flag) a[fa[q]].l=q;
else a[fa[q]].r=q;
}
update(p),update(q);
}
void splay(int x)
{
for(int f=fa[x];f;f=fa[x])
if(fa[f])
{
bool sonx=get(x),sonf=get(f);
if(sonx==sonf)//一条链的情况
{
if(!sonx) zig(fa[f]),zig(f);
else zag(fa[f]),zag(f);
}
else//中间有折点的情况
{
if(!sonx) zig(f),zag(fa[x]);
else zag(f),zig(fa[x]);
}
}
else
{
bool sonx=get(x);
if(!sonx) zig(f);
else zag(f);
}
root=x;
}
int insert(int &p,int f,int val)//插入操作，f为父亲，返回值为splay的点
{
if(!p)
{
p=New(val);
fa[p]=f;//这个别忘
return p;
}
if(val==a[p].val)
{
a[p].cnt++,a[p].Size++;
return p;
}
int res;
if(val<a[p].val) res=insert(a[p].l,p,val);
else res=insert(a[p].r,p,val);
update(p);
return res;
}
int getpre(int val)//找前驱
{
int ans=2;
int p=root;
while(p)
{
if(val==a[p].val)
{
if(a[p].l)
{
p=a[p].l;
while(a[p].r)p=a[p].r;
ans=p;
}
break;
}
if(a[p].val<val&&a[p].val>a[ans].val) ans=p;
p=val<a[p].val?a[p].l:a[p].r;
}
splay(ans);//这里可以直接splay，只会改变树的结构将ans变成root，但是不会改变ans存储的信息
return a[ans].val;
}
int getnext(int val)
{
int ans=1;
int p=root;
while(p)
{
if(val==a[p].val)
{
if(a[p].r)
{
p=a[p].r;
while(a[p].l)p=a[p].l;
ans=p;
}
break;
}
if(a[p].val>val&&a[p].val<a[ans].val) ans=p;
p=val<a[p].val?a[p].l:a[p].r;
}
splay(ans);//同上
return a[ans].val;
}
void remove(int val)
{
splay(getrank(root,val).second);//将删除的点splay到根
if(a[root].cnt>1)
{
a[root].cnt--,a[root].Size--;
return;
}
int L=a[root].l,R=a[root].r;
while(a[L].r) L=a[L].r;
//此时L一定没有右子树，而且是从a[root].l一直往右走得到的
splay(L);//此时L变成了根，原来的根为L的右子树，R为原来的根的子树
fa[R]=L,a[L].r=R;//由上面的分析直接O(1)修改没问题
update(L);
}
int main()
{
build();
scanf("%d",&n);
while(n--)
{
int opt,x,y;
pair<int,int> res;
scanf("%d%d",&opt,&x);
switch(opt)
{
case 1:
y=insert(root,0,x);
splay(y);
break;
case 2:
remove(x);
break;
case 3:
res=getrank(root,x);
printf("%d\n",res.first);
if(res.second!=-1) splay(res.second);
break;
case 4:
res=getval(root,x+1);
printf("%d\n",res.first);
splay(res.second);
break;
case 5:
printf("%d\n",getpre(x));
break;
case 6:
printf("%d\n",getnext(x));
break;
}
}
return 0;
}