Splay

旋转很大众，值得注意的是它的核心：伸展操作 Splay。其用途就是把结点 $u$ 转到 $v$ 的儿子位置，每步两格两格跳，每一步判断 $u$ 在 $\mathrm{fa}(u)$ 的位置和 $\mathrm{fa}(u)$ 在 $\mathrm{fa}(\mathrm{fa}(u))$ 位置。

	void update (int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; } 
	bool get (int x) { return x == ch[fa[x]][1]; } 
	void clear (int x) { sz[x] = fa[x] = ch[x][0] = ch[x][1] = val[x] = cnt[x] = 0; } 
	
	void rotate (int x) {
		int y = fa[x], z = fa[y], chid = get (x);
		ch[y][chid] = ch[x][chid ^ 1]; fa[ch[x][chid ^ 1]] = y;
		ch[z][get(y)] = x; fa[x] = z;
		ch[x][chid ^ 1] = y; fa[y] = x;
		update(y);
		update(x);
	}
	
	void splay (int x, int goal = 0) {
		for (int f = fa[x]; f = fa[x], f != goal; rotate(x))
			if (fa[f] != goal) rotate(get(x) == get(f)? f: x);
		if (!goal) root = x;
	}

之后每个操作都伸展一下保证复杂度。

还有一些较为特别的操作。

合并

合并两棵 Splay，其中一棵树的结点都小于另一个，把小树的最右点转到根，然后把大树放在其右子树。

可能感觉有个限制条件很鸡肋，实际上确实，但是可以用来维护删除操作。

分裂

以某元素所在结点为界分离树，转上来分类即可。

Link Cut Tree

实链剖分，Splay 维护实链以致动态，至于哪个点是实点看时间（换言之，由于其动态性，实点不是预先决定的）。

与 Splay 一样，LCT 也有一个的核心操作：access 操作。它提取一节点到原树根的路径。总之，将结点到根的路径设置为实链，其中序遍历从根开始、该节点结束。具体地，

1. 先把该节点伸展到实链根；
2. 把不在路径上的边变虚；
3. 把该节点的父亲（也就是非该链上原树的父亲）伸展到它的链的根，也把不在指定路径上的边变虚；
4. 往上并链：该点设为父亲的右儿子。
5. 循环直到根。

void access (int x) {
	for (int y = 0; x; y = x, x = t[x].fa) {
		splay (x); t[x].r = y;
		update(x);
		if (y) t[y].fa = x;
	}
} 

其它都围着 access 转。

板子