安利splay讲解：
【模板】普通平衡树（luogu）
Description
题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
- 插入 xx 数
- 删除 xx 数(若有多个相同的数，因只删除一个)
- 查询 xx 数的排名(排名定义为比当前数小的数的个数 +1+1 )
- 查询排名为 xx 的数
- 求 xx 的前驱(前驱定义为小于 xx，且最大的数)
- 求 xx 的后继(后继定义为大于 xx，且最小的数)
输入格式
第一行为 nn，表示操作的个数,下面 nn 行每行有两个数 \text{opt}opt 和 xx，\text{opt}opt 表示操作的序号( 1 \leq \text{opt} \leq 61≤opt≤6 )
输出格式
对于操作 3,4,5,63,4,5,6 每行输出一个数，表示对应答案
Code
#include <iostream>
using namespace std;
const int N=1e5+;
//1:插入xx数
//2:删除xx数(若有多个相同的数，因只删除一个)
//3:查询xx数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
//4:查询排名为xx的数
//5:求xx的前驱(前驱定义为小于xx，且最大的数)
//6:求xx的后继(后继定义为大于xx，且最小的数)
int n,x,opt,cnt[N],size[N],val[N],tot,ch[N][],rt,fa[N];
struct Splay
{
void push_up(int x)
{
size[x]=size[ch[x][]]+size[ch[x][]]+cnt[x];
}
bool get(int x)
{
return x==ch[fa[x]][];
}
void clear(int x)
{
size[x]=ch[x][]=ch[x][]=cnt[x]=val[x]=fa[x]=;
}
void rotate(int x)
{
int y=fa[x],z=fa[y],wh=get(x);
fa[ch[x][wh^]]=y;
ch[y][wh]=ch[x][wh^];
ch[x][wh^]=y;
fa[x]=z,fa[y]=x;
if(z) ch[z][y==ch[z][]]=x;
push_up(y),push_up(x);
}
void splay(int x)
{
for(int f=fa[x];f=fa[x],f;rotate(x))
if(fa[f]) rotate(get(f)==get(x)?f:x);
rt=x;
}
int nxt()
{
int now=ch[rt][];
while(ch[now][]) now=ch[now][];
return now;
}
int pre()
{
int now=ch[rt][];
while(ch[now][]) now=ch[now][];
return now;
}
int rk(int x)
{
int res=,now=rt;
while()
{
if(x<val[now]) now=ch[now][];
else
{
res+=size[ch[now][]];
if(x==val[now])
{
splay(now);
return res+;
}
res+=cnt[now],now=ch[now][];
}
}
}
int kth(int x)
{
int now=rt;
while()
{
if(ch[now][] && x<=size[ch[now][]]) now=ch[now][];
else
{
x-=size[ch[now][]]+cnt[now];
if(x<=) return val[now];
now=ch[now][];
}
}
}
void ins(int x)
{
if(!rt)
{
rt=++tot,cnt[tot]=,val[tot]=x;
push_up(tot);
return ;
}
int now=rt,par=;
while()
{
if(val[now]==x)
{
cnt[now]++;
push_up(now),push_up(par);
splay(now);
return ;
}
par=now,now=ch[now][x>val[now]];
if(!now)
{
cnt[++tot]=,val[tot]=x,fa[tot]=par;
ch[par][x>val[par]]=tot;
push_up(tot),push_up(par);
splay(tot);
return ;
}
}
}
void del(int x)
{
rk(x);
if(cnt[rt]>) cnt[rt]--,push_up(rt);
else if(!ch[rt][] && !ch[rt][]) clear(rt),rt=;
else if(!ch[rt][])
{
int now=rt;
rt=ch[rt][],fa[rt]=;
clear(now);
}
else if(!ch[rt][])
{
int now=rt;
rt=ch[rt][],fa[rt]=;
clear(now);
}
else
{
int x=pre(),now=rt;
splay(x);
fa[ch[now][]]=rt;
ch[rt][]=ch[now][];
clear(now);
push_up(rt);
}
}
}tree;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
while(n--)
{
cin>>opt>>x;
if(opt==) tree.ins(x);
else if(opt==) tree.del(x);
else if(opt==) cout<<tree.rk(x)<<endl;
else if(opt==) cout<<tree.kth(x)<<endl;
else if(opt==) tree.ins(x),cout<<val[tree.pre()]<<endl,tree.del(x);
else if(opt==) tree.ins(x),cout<<val[tree.nxt()]<<endl,tree.del(x);
}
return ;
}