速通 Splay

Splay 是 BST 稳定的一种方式，Splay 操作可以把一个节点转到根。

如果 $p$ 是根节点，那么直接对 $x$ 进行 zig 或者 zag:

如果 $x,p$ 在一侧，那么进行 zig-zig 或者 zag-zag 操作：

就是先将 $g$ 进行 zig 或者 zag，然后再把 $x$ 进行 zag 或者 zig 操作。

如果 $x,p$ 在异侧，那么进行 zig-zag 或者 zag-zig 操作：

就是先将 $x$ 先 zig 再 zag 或者先 zag 再 zig。

具体的，我们可以把 zig 操作和 zag 操作放到一起成为一个 rotate 操作。

LCT

基本思路

对于一棵树我们如果对它进行树链剖分，那么会有很多重链和一些非重链。

那么我们考虑更加自由的思考，如果我们可以指定一些边组成重链，那么就可以得到一个类似的东西，我们明明它为实链剖分。

我们令一些边组成的东西为实边，而剩下的单独则为虚边，那么就可以得到像下面这样的东西：

考虑用 Splay 去维护每一条实链，具体的把一个实链的深度作为权值放到一棵 Splay 中，显然这个Splay 的中序遍历就是这个实链从上到下依次遍历。

那么虚边怎么储存呢，每一个实链的头的 Splay 显然什么都没有，那么直接储存虚链就行了。

在最开始的，我们假设所有的边都是虚边，把每一个节点都开一个 Splay。

那么把这些 Splay 连接在一起得到的东西就是辅助树，其中虚边是不变的而 Splay 中的结构是可以改变的，比如下图就是上图的一种可能的辅助树。

一些变量

• ch[N][0/1]，左右儿子。
• f[N]，父亲。
• sum[N]，路径权值和。
• val[N] 点权。
• tag[N] 翻转标记。
• laz[N] 权值标记。
• siz[N] 辅助树上子树大小。

一些函数

线段树中有的

pushdown(x) 和 pushup(x)，字面意思。

Splay 中需要用的函数

1. get(x)，判断 $x$ 是其父亲的那一个儿子。
2. splay(x)，把 $x$ 转到根的位置。
3. retate(x)，把 $x$ 向上旋转一层。

宏定义

• #define ls ch[p][0]
• #define rs ch[p][1]

新函数的实现

简单函数

#define l(x) ch[(x)][0]
#define r(x) ch[(x)][1]
bool isRoot(int x){
	return l(fa[x])!=x&&r(fa[x])!=x;
}
void pushup(int x){
	s[x]=v[x]^s[l(x)]^s[r(x)];
	siz[x]=siz[l(x)]+siz[r(x)]+1;
}
void pushdown(int x){
	if(tag[x]){
		swap(l(x),r(x));
		tag[l(x)]^=1,tag[r(x)]^=1;
		tag[x]=0;
	}
}
void updata(int x){
	if(!isRoot(x)){
		updata(fa[x]);
	}
	pushdown(x);
}
bool get(int x){
	return ch[fa[x]][1]==x;
}
void rotate(int x){
	int y=fa[x],z=fa[y],k=get(x);
	if(!isRoot(y)){
		ch[z][ch[z][1]==y]=x;
	}
	ch[y][k]=ch[x][!k],fa[ch[x][!k]]=y;
	ch[x][!k]=y,fa[y]=x,fa[x]=z;
	pushup(y),pushup(x);
}
void splay(int x){
	updata(x);
	for(int f;f=fa[x],!isRoot(x);rotate(x)){
		if(!isRoot(f)){
			rotate(get(f)==get(x)?f:x);
		}
	}
	pushup(x);
}

Access()

对于一个树，可能长这样：

那么它的辅助树可能长成这样：

如果我们 Access(N) 就需要把根到 $N$ 放到一个 Splay 里面。

但是这时需要注意，我们需要把原树上 $A$ 到 $N$ 的这条路径都放到一起。

换而言之就是需要将所有红色的边修改：

考虑从下向上处理，显然我们需要先把 $N$ 旋转成为 Splay 的根，这样深度比 $N$ 小的就都在左儿子了。

显然 $N$ 的右儿子都是没有意义的，因为它们的深度是大于 $N$ 的，那么直接把右儿子设置为 $0$。

于是得到：

那么我们把 $N$ 的父亲旋转成上面的 Splay 的根节点，然后把 $N$ 设为 $I$ 的右儿子，得到：

继续把 $H$ 转成根节点，然后把 $I$ 设置成右儿子，得到：

再操作一次得到：

int access(int x){
	int p;
	for(p=0;x;p=x,x=fa[x]){
		splay(x),ch[x][1]=p;
		pushup(x);
	}
	return p;
}

其具体的步骤如下：

1. 把当前节点转到根。
2. 把儿子换成之前的节点。
3. 更新当前点的信息。
4. 把当前点换成当前点的父亲，继续操作。

这里提供的 Access 还有一个返回值，这个返回值相当于最后一次虚实链变换时虚边父亲节点的编号。

makeroot(x)

该函数可以改变原树上的根节点，可以处理路径的深度再特定的根下不不递增的情况。

• 设 Access(x) 的返回值为 $y$，则此时 $x$ 到当前根的路径恰好构成一个 Splay，且该 Splay 的根为 $y$。
• 考虑将树用有向图表示出来，给每条边定一个方向，表示从儿子到父亲的方向。容易发现换根相当于将 $x$ 到根的路径的所有边反向。
• 因此将 $x$ 到当前根的路径翻转即可。
• 由于 $y$ 是 $x$ 到当前根的路径所代表的 Splay 的根，因此将以 $y$ 为根的 Splay 树进行区间翻转即可。

void makeRoot(int x){
	x=access(x);
	tag[x]^=1;
}

link(x,y)

可以在 $x,y$ 之间添加一条边，那么 makeroot(x) 然后 splay(x) 就行了。

void link(int x,int y){
	makeRoot(x);
	splay(x);
	fa[x]=y;
}

Split(x,y)

把 $x,y$ 放到一个 Splay 中，直接 makeroot(x)，然后 Access(y) 就完了。

void split(int x,int y){
	makeRoot(x);
	access(y);
	splay(y);
}

Cut(x,y)

删除 $x,y$ 之间的连边，然后断开即可。

void cut(int x,int y){
	makeRoot(x);
	access(y);
	splay(y);
	l(y)=fa[x]=0;
}

Find()

Find(x) 查找的是 $x$ 所在的 原树 的根，请不要把原树根和辅助树根弄混。

在 Access(p) 后，再 Splay(p)。这样根就是树里深度最小的那个，一直往左儿子走，沿途 PushDown 即可。

一直走到没有 $ls$，非常简单。

注意，每次查询之后需要把查询到的答案对应的结点 Splay 上去以保证复杂度。

int find(int x){
	access(x);
	splay(x);
	pushdown(x);
	while(l(x)){
		x=l(x),pushdown(x);
	}
	splay(x);
	return x;
}