不打算详细写了，强推一波 yyb 神仙的博客 Splay入门解析【保证让你看不懂（滑稽）】
（这篇博客的代码完全是按照 yyb 的博客写的，并有一些补充，包括 pushup 及查询第 k 大的整数等等）
这里列几个注意事项吧：
-
\(Splay\) 过程中，如果 \(x, y\) 为同一种儿子，那么先旋转 \(y\)，再转 \(x\)，否则旋转两次 \(x\)。
-
rotate时的顺序：- 先改 \(z\) 的儿子（\(z\) 的儿子从 \(y\) 变成 \(x\)）
- 再改 \(x\) 的儿子中变动的那个儿子（从 \(x\) 的儿子变成 \(y\) 的儿子，至于是哪个建议背过，背不过的话现推一下规律）
- 最后令 \(y\) 变成 \(x\) 的儿子。
-
pushup不要忘记写。 -
pushup的过程是先儿子，再父亲（不要哪个顺手先写哪个 QwQ）。 -
find函数中，\(x\) 可能还有父亲节点的原因：树上没有权值为 \(x\) 的点，\(splay\) 一次之后转到根的点的权值小于 \(x\)，所以会有父亲节点。 -
上面的这个问题在查 \(x\) 的排名时同样会出现，就是当前的树根权值可能小于 \(x\)，所以输出答案时要特判一下是否加上树根的
cnt。
（洛谷上的普通平衡树没这问题，但是加强版有问题，事实上这里不改的话样例都过不了。）
emm……别的似乎就没了。
（以后有时间的话可能会稍微写的详细一点，先咕了）
\(Code:\)
（原题是洛谷 P3369，代码里有较为详细的注释）
#include <bits/stdc++.h>
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
using namespace std;
namespace IO{
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
template <typename T> inline void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 1e6 + 10;
int n;
struct splay{
int val, siz, fa, ch[2], cnt;
}t[N];
int root, tot;
inline void pushup(int x){
t[x].siz = t[ls(x)].siz + t[rs(x)].siz + t[x].cnt;
}
//旋转
inline void rotate(int x){
int y = t[x].fa, z = t[y].fa;
int k = (rs(y) == x);// 0 是左儿子，1 是右儿子
t[z].ch[(rs(z) == y)] = x;//z 原来的 y 位置变成 x
t[x].fa = z;
t[y].ch[k] = t[x].ch[k ^ 1];//x 的另一个儿子变成 x 在 y 原本位置上的儿子
t[t[x].ch[k ^ 1]].fa = y;//更新父亲
t[x].ch[k ^ 1] = y, t[y].fa = x;//更新 x 和 y 的关系
pushup(y), pushup(x);
}
//核心 splay
inline void splay(int x, int goal){
while(t[x].fa != goal){
int y = t[x].fa, z = t[y].fa;
if(z != goal) rotate((ls(z) == y) ^ (ls(y) == x) ? x : y);//splay 双旋分类讨论
rotate(x);
}
if(!goal) root = x;
}
//查找 x 的位置，并 splay 到根
inline void find(int x){
int u = root;
if(!u) return;
while(t[u].ch[x > t[u].val] && x != t[u].val) u = t[u].ch[x > t[u].val];//小于 -> 往左跳，大于 -> 往右跳
splay(u, 0);
}
//插入一个新节点
inline void insert(int x){
int u = root, fa = 0;
while(u && t[u].val != x) fa = u, u = t[u].ch[x > t[u].val];//找到等于 x 的点
if(u) t[u].cnt++;//如果有，计数 +1
else{
u = ++tot;//没有，新建节点
if(fa) t[fa].ch[x > t[fa].val] = u;
t[u].ch[0] = t[u].ch[1] = 0;
t[u].siz = t[u].cnt = 1, t[u].val = x, t[u].fa = fa;
}
splay(u, 0);
}
//查询 前驱/后继
inline int check(int x, int type){//type = 0 前驱，1 后继
find(x);
int u = root;//根节点，此时 x 的父节点（存在的话）就是根节点
if((t[u].val > x && type) || (t[u].val < x && !type)) return u;
u = t[u].ch[type];
while(t[u].ch[type ^ 1]) u = t[u].ch[type ^ 1];//反着跳
return u;
}
//删除
inline void remove(int x){
int lst = check(x, 0), nxt = check(x, 1);//查 前驱/后继
splay(lst, 0), splay(nxt, lst);//前驱 splay 到根，后继 splay 到前驱，x 是后继的左子节点，且是叶节点
int del = ls(nxt);
if(t[del].cnt > 1) t[del].cnt--, splay(del, 0);//如果个数 > 1, 直接--
else t[nxt].ch[0] = 0;//只有一个，删掉 nxt 的左儿子
pushup(nxt), pushup(lst);
}
//查询第 k 大
inline int get_val(int x, int k){
if(k <= t[ls(x)].siz) return get_val(ls(x), k);
else if(k > t[ls(x)].siz + t[x].cnt) return get_val(rs(x), k - t[ls(x)].siz - t[x].cnt);
else return t[x].val;
}
int main(){
n = read();
insert(-2147483647), insert(2147483647);
for(int i = 1; i <= n; ++i){
int op = read(), x = read();
if(op == 1) insert(x);
else if(op == 2) remove(x);
else if(op == 3) find(x), write(t[ls(root)].siz), puts("");
else if(op == 4) write(get_val(root, x + 1)), puts("");
else if(op == 5) write(t[check(x, 0)].val), puts("");
else write(t[check(x, 1)].val), puts("");
}
return 0;
}
\[\_EOF\_
\]