引子

在古老且美妙的数据结构王国，一次，一个巨大的怪兽出现在了这个国家，这个怪兽是一棵树，打败这个怪兽只需要能快速求出这个怪兽任意一条路径上的和就可以了，可是他灵活多变，自己的手脚可以调换位置，或拿下来（边可以断掉或连上）身上的每一寸肌肤都可改变其硬度（点可以修改值）

树链剖分找到了$splay$，他们决定联手，树链剖分将这个怪兽分成一条条的链，让$splay$去套在链上，无论怪兽怎样变化，$splay$都可以去维护这条链，怪兽就这样被打败了

这是怎么做到的呢？？

$aqz180321$今天比较疯狂，决定研究一下

前置芝士

splay

主要用到他的翻转区间和将任意一个节点旋转到根的功能

树链剖分

了解思想就可以

正题

传送门

我们先对其进行实链剖分

对于一个点连向它所有儿子的边，我们自己任意选择一条边进行剖分，我们称被选择的边为实边，其他边则为虚边。

对于实边，我们称它所连接的儿子为实儿子。对于一条由实边组成的链，我们同样称之为实链。

请记住我们选择实链剖分的最重要的原因：它是我们选择的，灵活且可变。正是它的这种灵活可变性，我们采用 $Splay Tree$ 来维护这些实链。

$--$ oi-wiki

如

实链有：

$A-B-C$
$C-E$
$F$

我们对于每一颗实链都建一棵$splay$树

$splay$树中通过深度进行的划分，也就是说 $lson$的深度 $<$ 当前节点的深度 $<$ $rson$ 的深度

不难发现，这颗$splay$树的中序遍历的结果，相当于从上到下遍历这条链

如下图

然后将这些$splay$树的根指向在原树中 这条链 的父亲节点（即链最顶端的点（即深度最小的点）的父亲节点）

如图

我们将这样构成的树叫做辅助树

然后这就是他的初步，~~是不是感觉挺简单的~~，他的神通之处是在他的函数

只有几个函数而已

函数

前提：变量名

$ch[x][0]$ 左儿子(对于splay中)

$ch[x][1]$ 右儿子(对于splay中)

$fa[x]$ 父亲(对于辅助树中)

因为对于的树不同，所以会出现一种情况：

它的辅助树可能长这样：

其中$fa[D] = B$,但是$ch[B][0] = A$ $ch[B][1] = E$均不是$D$

说人话就是，任何儿子认父亲，但是父亲只认实儿子(因为实儿子和父亲在一条实链中即在一棵$splay$中)

所以可以根据这个特性去判断当前节点是否为$splay$的根

bool isroot (int x) {
	return x != ch[fa[x]][0] && x != ch[fa[x]][1];
}

$tag[x]$ 翻转标记，同文艺平衡树中的区间翻转操作中的标记

实链剖分的变量：

$sum[x]$ 链的和

$val[x]$ 当前节点的值

isroot

上文说过了

pushup

链维护和的函数

void pushup (int x) {
	sum[x] = sum[ch[x][0]] ^ sum[ch[x][1]] ^ val[x];
}

模板题中是异或和，所以这里是异或

reverse

翻转，同文艺平衡树

void reverse (int x) {
	std::swap(ch[x][0], ch[x][1]);
	tag[x] ^= 1;
}

pushdown

下放翻转标记，同文艺平衡树

void pushdown (int x) {
	if (tag[x]) {
		if (ch[x][0]) reverse(ch[x][0]);
		if (ch[x][1]) reverse(ch[x][1]);
		tag[x] = 0;
	}
}

update

从当前节点一直到根节点递归下放翻转标记

void update (int x) {
	if (!isroot(x)) update(fa[x]);
	pushdown(x);
}

rotate

$spaly$中的旋转

void rotate (int x) {
	int y = fa[x], z = fa[y], kth = get(x);
	if (!isroot(y)) ch[z][y == ch[z][1]] = x;//特别注意的地方
	ch[y][kth] = ch[x][kth ^ 1];
	fa[ch[x][kth ^ 1]] = y;
	ch[x][kth ^ 1] = y;
	fa[y] = x;fa[x] = z;
	pushup(y), pushup(x);
}

旋转一定不能超过当前的$splay$即超过根

splay

$spaly$中的旋转到根

void splay (int x) {
	update(x);//释放旋转标记
	for (int f; f = fa[x], !isroot(x); rotate(x))
		if (!isroot(f)) rotate(get(f) == get(x) ? f : x);
       //注意不要超出根
}

~~是不是挺简单的~~

接下来是LCT的精华，笔者已经冲疯了

access

将当前节点到根连一条实链，实链使我们规定的链，所以会很灵活

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

什么，这么简单？？？但是很抽象

可以见$oi-wiki$的演示

传送门

这里就文字描述一下

从根到一个节点路径应该是唯一的，深度也是递增的

首先将$x$旋转到根，这是$ch[x][0]$就是深度比他小的，这些是要的，因为是从根到当前节点，这些节点肯定经过，所以$ch[x][1]$就可以不要了故可以将$ch[x][1] = p$ ，$pushup$修改一下，然后$p = x, x = fa[x]$去到他的父亲，父亲也是深度比他大的，所以也要，但是父亲所在的$splay$中有不合法的，所以去搞他的父亲，搞完之后，将自己没有用的$ch[x][1]$连上，这颗平衡树深度大小关系也是满足的

笔者能力有限，只能描述成这样

它执行以后，辅助树改变了，但是原树没有改变，只是改变了原树的实链的划分

makeroot

成为根，原树是一棵无根树，所以根可以是任意一个

先从根节点到要成为根的节点变成实链，在将当前节点旋到最上面，因为当前节点是深度最小的，所有右儿子为空，翻转儿子，左儿子为空，就成为了深度最小的点，即根

void makeroot (int x) {
	access(x);splay(x);
	reverse(x);
}

findroot

找辅助树的根，先把根节点到要找根的节点变成实链，再将当前节点旋转到上边，最后一直向左找，最左边就是深度最小的，即是根

最后在把根旋转上来，方便以后操作

int findroot (int x) {
	access(x);splay(x);
	while (ch[x][0]) pushdown(x), x = ch[x][0];
	splay(x);
	return x;
}

split

将x到y的路径变成实链

先把x变成根，在从根向y连一条实链就可以了，最后将y旋转上去，方便以后查询

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

link

将x和y连边，这就会对原树造成影响了与上边的split有很大的区别

先将x变成根，再看看y是否和x在一个辅助树内（即是否在一个原树内），如果没有，此时x是根，父亲是空的，就可以将父亲指向y

void link (int x, int y) {
	makeroot(x);
	if (findroot(y) != x) fa[x] = y;
}

cut

将x和y的边删除

首先将x变成根，判断x和y在原树中是否是父子关系

注意！if语句中的findroot函数干了很多事情，首先x和y成为了一条链（因为x此时是根）x又回到了所在splay树的根节点

上文我们说过，splay树的中序便利就是原树从上到下的便利，所以x和y在原树是父子关系，他们的便利是紧挨着的，所以判断$fa[y] == x $ && $ !ch[y][0]$ 才能保证中序遍历是紧挨着的（先便利左子树，在输出当前，在便利右子树）

最后就双向奔赴，fa和ch全部清零就可以了

void cut (int x, int y) {
	makeroot(x);
	if (findroot(y) == x && fa[y] == x && !ch[y][0]) {
		fa[y] = ch[x][1] = 0;
		pushup(x);
	}
}

主函数

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", val + i);
	for (int i = 1, op, x, y; i <= m; i++) {
		scanf("%d%d%d", &op, &x, &y);
		switch (op) {
			case 0: split(x, y);printf("%d\n", sum[y]);break;
			case 1: link(x, y);break;
			case 2: cut(x, y);break;
			case 3: splay(x);val[x] = y;break;
		}
	} 
	return 0;
}

查询，就先将x到y连一条链，因为split的最后y变成了根，所以直接输出y就可以了

修改，需要先将x变成根，他的修改才不会影响任何人