不打算详细写了，强推一波 yyb 神仙的博客 Splay入门解析【保证让你看不懂（滑稽）】
（这篇博客的代码完全是按照 yyb 的博客写的，并有一些补充，包括 pushup 及查询第 k 大的整数等等）
这里列几个注意事项吧：
-
过程中，如果 为同一种儿子，那么先旋转 ，再转 ，否则旋转两次 。
-
rotate时的顺序：- 先改 的儿子（ 的儿子从 变成 ）
- 的儿子中变动的那个儿子（从 的儿子变成 的儿子，至于是哪个建议背过，背不过的话现推一下规律）
- 最后令 变成 的儿子。
（另外，不要忘记改父亲的编号）
-
pushup不要忘记写。 -
pushup的过程是先儿子，再父亲（不要哪个顺手先写哪个 QwQ）。
emm……别的似乎就没了。
（以后有时间的话可能会稍微写的详细一点，先咕了）
（原题是洛谷 P3369，代码里有较为详细的注释）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
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;
}
