初学Splay注释多

记录

看了数据#14 先是插入超级多的数，然后又问了超级多的rank

是不是问rank 时没有 Splay(x, 0) 导致的

Code：

//【模板】普通平衡树
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::ios;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using db = double;
using ldb = long double;
using str = std::string;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define pre(i, a, b) for(int i = (a); i >= (b); --i)
#define mp make_pair
#define ft first
#define sd second
#define ppb pop_back
#define ppf pop_front
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ef emplace_front
#define clr clear
#define ins insert
#define ers erase
#define Mem(a, b) memset(a, b, sizeof a)
#define Copy(a, b) memcpy(a, b, sizeof b)
#define Debug(x) std::cerr << #x << '=' << x << ' '
#define File(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
// #define int ll
// #define double ldb
#define il inline
il int Read(int &x) {
	x = 0;
	int f = 1;
	char ch = getchar();
	for(; !isdigit(ch); ch = getchar())
		if(ch == '-') f = -1;
	for(; isdigit(ch); ch = getchar())
		x = x * 10 + ch - '0';
	return x = x * f;
}
template<typename Tp> il void Write(Tp x) {
	if(x < 0) x = -x, putchar('-');
	static char stk[42];
	short top = 0;
	do {
		stk[++top] = x % 10 + '0';
		x /= 10;
	} while(x);
	while(top) putchar(stk[top--]);
}
const int N = 1e5 + 10, INF = 1e9;
int n;
template<typename Tp, const int N>
class SplayTreap { // Splay 伸展树
  private:
	int root, cnt;
	struct Node {
		int fa, son[2];
		Tp val;
		int size;
		Node() { fa = son[0] = son[1] = val = size = 0; }
	} t[N];
#define ls(p) t[p].son[0]
#define rs(p) t[p].son[1]
#define fa(p) t[p].fa
	il void Rotate(int x) { // 核心旋转
		int y = t[x].fa, z = t[y].fa; // 记录父亲和爷爷
									// 右旋；左旋
		int c = (t[y].son[0] == x); // 左儿子 c 为 1；右儿子 c 为 0
		t[y].son[c ^ 1] = t[x].son[c]; // x 的右儿子是 y 的左儿子；x 的左儿子是 y 的右儿子
		t[t[x].son[c]].fa = y; // 标记 fa
		t[x].fa = z; // 旋转后 x 的父亲是 z
		if(z != 0) // 如果 z 有值，说明 x 不是根节点
			t[z].son[t[z].son[1] == y] = x;
			// 如果原来 y 是 z 的左儿子，那么现在 x 就是 z 的左儿子
			// 如果原来 y 是 z 的右儿子，那么现在 x 就是 z 的右儿子
		t[x].son[c] = y;
		// 如果原来 x 是 y 的左儿子，那么现在 y 是 x 的右儿子
		// 如果原来 x 是 y 的右儿子，那么现在 y 是 x 的左儿子
		t[y].fa = x; // 标记 fa
		Update(y);
		Update(x);
	}
	il void Splay(int x, int goal) { // 双层伸展，把 x 旋转为 goal 的儿子
		while(t[x].fa != goal) {
			int y = t[x].fa, z = t[y].fa;
			if(z != goal) {
				(ls(z) == y) ^ (ls(y) == x) ? Rotate(x) : Rotate(y);
				// 如果 x，y 是 y，z 的异向儿子（之字型），就旋转 x
				// 如果 x，y 是 y，z 的同向儿子（一字型），就旋转 y
			}
			Rotate(x);
			// 如果 z 就是 goal 的话旋转 x 即可
			// 如果不是就要转两次
		}
		if(goal == 0) root = x;
	}	
	il int NewNode(int fa, Tp val) { // 新点
		t[++cnt].fa = fa;
		t[cnt].val = val;
		t[cnt].son[0] = t[cnt].son[1] = 0;
		t[cnt].size = 1;
		return cnt;
	}
	il void Update(int x) { // 更新子树大小
		t[x].size = 1;
		if(ls(x) != 0) t[x].size += t[ls(x)].size; 
		if(rs(x) != 0) t[x].size += t[rs(x)].size; 
	}
	il int FindMax(int x = -1) { // 查找最大值节点
		if(x == -1) x = root;
		while(rs(x) != 0) x = rs(x); // 一直往右边走
		return x;
	}
	il int FindMin(int x = -1) { // 查找最小值节点
		if(x == -1) x = root;
		while(ls(x) != 0) x = ls(x); // 一直往左边走
		return x;
	}
	il bool Split(Tp val, int &t1, int &t2) { // 将整棵树分裂成两棵子树
		if(!Find(val)) return false; // 没找到 val
		// 找到了 val
		t1 = ls(root), t2 = rs(root);
		if(t1 != 0) t[t1].fa = 0;
		if(t2 != 0) t[t2].fa = 0;
		ls(root) = rs(root) = 0; // 断开原根节点
		return true;
	}
	il void Merge(int t1, int t2) { // 合并两棵子树
		if(t1 == 0) {
			root = t2;
			return;
		}
		if(t2 == 0) {
			root = t1;
			return;
		}
		Splay(FindMax(t1), 0);
		rs(root) = t2;
		t[t2].fa = root;
		Update(root);
	}
  public:
	il SplayTreap() { Clear(); }
	il void Clear() {
		root = cnt = 0;
		t[root].son[0] = t[root].son[1] = 0;
	}
	il int Find(Tp val) { // 在伸展树中查找 val
		int x = root;
		while(true) {
			if(t[x].val == val) { // 找到了
				Splay(x, 0); // 把 x 旋转到根
				return x;
			}
			int &next = t[x].son[t[x].val < val];
			if(next != 0)
				x = next;
			// 如果 t[x].val < val 说明该往右儿子找
			// 如果 t[x].val > val 说明该往左儿子找
			else break; // 没找到又不能往下走，说明没有
		}
		return Tp();
	}
	il void Insert(Tp val) { // 在伸展树中插入 val
		if(root == 0) {
			root = NewNode(0, val);
			return;
		}
		int x = root;
		while(true) {
			int &next = t[x].son[t[x].val < val];
			if(next != 0) // 找到
				x = next;
			else {
				next = NewNode(x, val); // 插入
				Splay(next, 0); // 将新节点旋转到根
				return;
			}
		}
	}
	il void Remove(Tp val) { // 删除值为 val 的点
		int x = Find(val);
		if (x == 0) return;
		int t1 = ls(x), t2 = rs(x);
		fa(t1) = fa(t2) = 0;
		if (t1 != 0) {
			Splay(FindMax(t1), 0);
			rs(root) = t2;
			if (t2 != 0) fa(t2) = root;
			Update(root);
		} else root = t2;
	}
	il int Rank(Tp val) { // 查排名
		int x = root;
		int rank = 0;
		while(x != 0) {
			if(t[x].val < val) { // 去右儿子
				rank += t[ls(x)].size + 1;
				x = rs(x);
			}
			else x = ls(x);
		}
		return rank + 1;
	}
	il Tp Kth(int k) { // 查询第 k 大
		int x = root;
		while(x != 0) {
			int lsize = t[ls(x)].size;
			if(lsize + 1 == k) { // 找到了
				Splay(x, 0);
				return t[x].val;
			}
			else if(lsize >= k)
				x = ls(x);
			else {
				k -= (lsize + 1);
				x = rs(x);
			}
		}
		return Tp();
	}
	il Tp Prev(Tp val) { // 查询前驱
		int x = root;
		Tp prev = -INF;
		while(x != 0) {
			if(t[x].val < val) {
				if(t[x].val > prev)
					prev = t[x].val;
				x = rs(x);
			} else x = ls(x);
		}
		return prev;
	}
	il Tp Next(Tp val) {// 查询后继
		int x = root;
		Tp next = INF;
		while (x != 0) {
			if (t[x].val > val) {
				if (t[x].val < next) next = t[x].val;
				x = ls(x);
			} else x = rs(x);
		}
		return next;
	}
#undef ls
#undef rs
};
SplayTreap<int, N> T;
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	Read(n);
	while(n--) {
		int opt, x;
		Read(opt), Read(x);
		switch(opt) {
			case 1: T.Insert(x); break;
			case 2: T.Remove(x); break;
			case 3: Write(T.Rank(x)), putchar('\n'); break;
			case 4: Write(T.Kth(x)), putchar('\n'); break;
			case 5: Write(T.Prev(x)), putchar('\n'); break;
			case 6: Write(T.Next(x)), putchar('\n'); break;
		}
	}
	return 0;
}