不打算详细写了，强推一波 yyb 神仙的博客 Splay 入门解析【保证让你看不懂（滑稽）】
（这篇博客的代码完全是按照 yyb 的博客写的，并有一些补充，包括 pushup 及查询第 k 大的整数等等）
这里列几个注意事项吧：
过程中，如果 为同一种儿子，那么先旋转 ，再转 ，否则旋转两次 。
rotate时的顺序：- 先改 的儿子（ 的儿子从 变成 ）
- 的儿子中变动的那个儿子（从 的儿子变成 的儿子，至于是哪个建议背过，背不过的话现推一下规律）
- 最后令 变成 的儿子。
（另外，不要忘记改父亲的编号）
pushup不要忘记写。pushup的过程是先儿子，再父亲（不要哪个顺手先写哪个 QwQ）。
emm…… 别的似乎就没了。
（以后有时间的话可能会稍微写的详细一点，先咕了）
（原题是洛谷 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; | |
} |
