前言
splay学了已经很久了，只不过一直没有总结，鸽了好久来写一篇总结。
先介绍 splay：亦称伸展树，为二叉搜索树的一种，部分操作能在 ）
也可以参照这段代码将一些操作写为非递归的写法，会更快一些。
总结
有些细心的同学可能已经发现了，几乎每个操作都有 splay 操作来维护当前树的形态，保证时间复杂度。
C++代码
只是将上述操作拼起来放在一个代码里。
说明一下操作的几种类型：
- 插入 \(x\) 数。
- 删除 \(x\) 数(若有多个相同的数，因只删除一个)。
- 查询 \(x\) 数的排名(排名定义为比当前数小的数的个数 \(+1\) )。
- 查询排名为 \(x\) 的数。
- 求 \(x\) 的前驱(前驱定义为小于 \(x\)，且最大的数)。
- 求 \(x\) 的后继(后继定义为大于 \(x\)，且最小的数)。
不是特别长，实现的方法也并不困难，打的时候必须得注意，完整没附上注释的代码：
#include <cstdio>
namespace Quick_Function {
template <typename Temp> void Read(Temp &x) {
x = 0; char ch = getchar(); bool op = 0;
while(ch < '0' || ch > '9') { if(ch == '-') op = 1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
if(op) x = -x;
}
template <typename T, typename... Args> void Read(T &t, Args &... args) { Read(t); Read(args...); }
template <typename Temp> Temp Max(Temp x, Temp y) { return x > y ? x : y; }
template <typename Temp> Temp Min(Temp x, Temp y) { return x < y ? x : y; }
template <typename Temp> Temp Abs(Temp x) { return x < 0 ? (-x) : x; }
template <typename Temp> void Swap(Temp &x, Temp &y) { x ^= y ^= x ^= y; }
}
using namespace Quick_Function;
#define INF 0x3f3f3f3f
const int MAXN = 1e6 + 5;
int n;
struct Splay_Node {
int son[2], val, cnt, siz, fa;
#define ls t[pos].son[0]
#define rs t[pos].son[1]
};
struct Splay_Tree {
int root, tot;
Splay_Node t[MAXN];
bool Ident(int pos) { return t[t[pos].fa].son[1] == pos; }
int New(int val, int fa) {
t[++tot].fa = fa, t[tot].cnt = t[tot].siz = 1, t[tot].val = val;
return tot;
}
void Build() { root = New(-INF, 0); t[root].son[1] = New(INF, root); }
void Update(int pos) { t[pos].siz = t[ls].siz + t[rs].siz + t[pos].cnt; }
void Connect(int pos, int fa, int flag) { t[fa].son[flag] = pos, t[pos].fa = fa; }
void Rotate(int pos) {
int fa = t[pos].fa, grand = t[fa].fa;
int flag1 = Ident(pos), flag2 = Ident(fa);
Connect(pos, grand, flag2);
Connect(t[pos].son[flag1 ^ 1], fa, flag1);
Connect(fa, pos, flag1 ^ 1);
Update(fa); Update(pos);
}
void Splay(int pos, int to) {
for(int fa = t[pos].fa; t[pos].fa != to; Rotate(pos), fa = t[pos].fa)
if(t[fa].fa != to) Ident(pos) == Ident(fa) ? Rotate(fa) : Rotate(pos);
if(!to) root = pos;
}
int Find(int pos, int val) {
if(!pos) return 0;
if(val == t[pos].val) return pos;
else if(val < t[pos].val) return Find(ls, val);
else return Find(rs, val);
}
void Insert(int &pos, int val, int fa) {
if(!pos) Splay(pos = New(val, fa), 0);
else if(val == t[pos].val) { ++t[pos].cnt; Splay(pos, 0); }
else if(val < t[pos].val) Insert(ls, val, pos);
else Insert(rs, val, pos);
}
void Erase(int val) {
int pos = Find(root, val);
if(!pos) return;
if(t[pos].cnt > 1) { --t[pos].cnt; Splay(pos, 0); return; }
Splay(pos, 0);
int l = ls, r = rs;
while(t[l].son[1]) l = t[l].son[1];
while(t[r].son[0]) r = t[r].son[0];
Splay(l, 0); Splay(r, l);
t[r].son[0] = 0;
}
int Query_kth(int pos, int val) {
if(!pos) return 0;
if(val == t[pos].val) { int res = t[ls].siz + 1; Splay(pos, 0); return res; }
else if(val < t[pos].val) return Query_kth(ls, val);
int res = t[ls].siz + t[pos].cnt;
return Query_kth(rs, val) + res;
}
int Query_val(int pos, int rank) {
if(!pos) return INF;
if(t[ls].siz >= rank) return Query_val(ls, rank);
else if(t[ls].siz + t[pos].cnt >= rank) { Splay(pos, 0); return t[pos].val; }
return Query_val(rs, rank - t[ls].siz - t[pos].cnt);
}
int Get_Pre(int val) {
int pos, res, newroot;
pos = newroot = root;
while(pos) {
if(t[pos].val < val) { res = t[pos].val; pos = rs; }
else pos = ls;
}
Splay(newroot, 0);
return res;
}
int Get_Nxt(int val) {
int pos, res, newroot;
pos = newroot = root;
while(pos) {
if(t[pos].val > val) { res = t[pos].val; pos = ls; }
else pos = rs;
}
Splay(newroot, 0);
return res;
}
};
Splay_Tree tree;
int main() {
tree.Build(); Read(n);
for(int i = 1, opt, x; i <= n; i++) {
Read(opt, x);
if(opt == 1) tree.Insert(tree.root, x, 0);
else if(opt == 2) tree.Erase(x);
else if(opt == 3) printf("%d\n", tree.Query_kth(tree.root, x) - 1);
else if(opt == 4) printf("%d\n", tree.Query_val(tree.root, x + 1));
else if(opt == 5) printf("%d\n", tree.Get_Pre(x));
else printf("%d\n", tree.Get_Nxt(x));
}
return 0;
}