lp3690 【模板】Link Cut Tree （动态树）

树链剖分有多种方法。例如以重量为关键字的重链剖分，以长度为关键字的长链剖分。
而LCT（Link-Cut-Tree）就是一种特殊的利用Splay维护树的剖分结构的算法。
我们称一棵树上连接同一条链的边为实边，连接不同的链的边为虚边，那么这棵树就被分成了许多链。我们称这种剖分方法为实链剖分。
由于实链剖分的虚实是可以动态变化的，因此它具有很多用途。比如动态维护连通性、换根等等操作。
下面我们大致地考虑如何用Splay维护LCT实现实链剖分。

对于实链剖分剖出的每一条链，它总是一条自上往下的链。形式化地说，链中的节点的深度连续且各不相同。
对于原树剖分出的每一条链，我们建一棵Splay维护这棵树。每个点在Splay上的权值是这个点在原树上的深度。这样，无论Splay的结构如何改变，这棵Splay始终维护的是一条链。
对于每棵Splay，我们设它的父亲为整个链的最顶端节点的父亲。
对于原树中的一条实边，由于它位于Splay中，所以它对应着Splay中的一组前驱-后继关系。
对于原树中的一条虚边，它连接的两个节点中的一个节点对应的是两条链之间的连接。位于较下方的那条链对应的Splay的父亲显然指向的是位于较上方的那个节点；而位于较上方的那个节点却不必指向位于较下方的那个节点。这条性质被称为「认父不认子」。

access(Y)
显然，在维护信息的时候，原图上的实链结构并不总是能让我们满意。这时候我们需要从根到Y将树上的某一条竖直的链变成实链，并且不改变它原来的性质。这要怎么做呢？
我们设计一个access（接驳）函数，来完成这个过程。
对于路径上的第一条需要变成实边的虚边，我们是容易找到的——这便是Y所在的Splay的根节点连向其父亲的边。当然，这需要我们将Y旋到其所在的Splay的根。
我们将Y所在的Splay的根的父亲A也旋到其所在的Splay的根，那么它原本的实子链在Splay上正好是它的右子树。所以，我们将它的右子节点改为Y节点。那么，A-Y是已经成为了一条满足操作要求的实链，于是问题就转化为了将A-X转化为实链的子问题。
于是依次向上修改即可。

chgrt(X)
在实际操作中，我们操作的链并不总是从某个节点到根的一条链。这时候我们需要换根操作。
首先，我们将根节点到将要成为根的节点X置于同一条实链上——这可以通过access来达成。
在access后，X便是X所在的Splay中原树深度最浅的节点，也就是最右的节点。这时候，倘若将X旋到其所在的Splay的根，然后翻转X，那么整条链就上下倒转了。

qryrt(X)
在确认连通性的时候，我们需要询问某个点X所在的树的根。
显然，这要求的就是access之后X所在的Splay的最左端节点。

split(X,Y)
在处理具体操作的时候，我们可能会需要将某一条链摘离出来。
如果它们连通，只需要换根到一者，然后access另一者即可。

link(X,Y)
从X到Y连边。
方法很简单，将X作为它所在的树的根，然后直接连一条虚边即可。

cut(X,Y)
删除X和Y之间的边。
倘若保证X和Y之间本来是有连边的，那倒是容易了，直接split出来之后分离两者即可。
现在我们需要考虑两者没有连边的情况。
首先，我们将X变为根，然后寻找Y的根。
考虑Splay操作的影响，我们知道，这样操作之后，在Splay树上，Y节点一定在X节点的右儿子的位置。
在这种情况下，如果Y的根不是X，那么显然两者不连通。如果Y不是X的后继，那么显然两者之间有隔着点，也就不是父子关系。

注意：
一：关于Splay：在LCT中，我习惯使用的SplayOne的方法并不是特别有效，这是因为在LCT中存在虚边。
二：在旋转的时候，需要特别注意判断C是空节点和Y是根节点的情况。在这两种情况下有两句话是不应该写的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=300005;
int fa[N],ch[N][2],rev[N],sm[N],val[N];

inline bool isrt(int X){
	return ch[fa[X]][0]!=X&&ch[fa[X]][1]!=X;
}
inline void updt(int X){
	sm[X]=sm[ch[X][0]]^sm[ch[X][1]]^val[X];
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void pshd(int X){
	if(rev[X]){
		if(ch[X][0]){
			flp(ch[X][0]);
		}
		if(ch[X][1]){
			flp(ch[X][1]);
		}
		rev[X]=0;
	}
}
inline int fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
//	int D=fndD(X),D2=fndD(fa[X]);
//	fa[ch[X][D^1]]=fa[X],ch[fa[X]][D]=ch[X][D^1];
//	ch[X][D^1]=fa[X],fa[X]=fa[ch[X][D^1]];
//	ch[fa[X]][D2]=X,fa[ch[X][D^1]]=X;
//	updt(ch[X][D^1]),updt(X);
//	在LCT中，我习惯使用的SplayOne的方法并不是特别有效，这是因为在LCT中存在虚边。
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(fa[X]),C=ch[X][D^1];
	if(!isrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[X]=Z,fa[Y]=X;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(!isrt(Y)){
		Y=fa[Y];
		st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(!isrt(X)){
		Y=fa[X],Z=fa[Y];
		if(!isrt(Y)){
			splayOne((fndD(X)^fndD(Y))?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline int qryrt(int X){
	access(X),splay(X);
	while(ch[X][0]){
		pshd(X);
		X=ch[X][0];
	}
	splay(X);
	return X;
} 
inline void split(int X,int Y){
	chgrt(X);
	access(Y),splay(Y);
} 
inline bool link(int X,int Y){
	chgrt(X);
	if(qryrt(Y)==X){
		return 0;
	}
	fa[X]=Y;
	return 1;
}
inline bool cut(int X,int Y){
	split(X,Y);
	if(ch[Y][0]!=X||ch[X][1]){
		return 0;
	}
	fa[X]=ch[Y][0]=0;
	return 1;
}
int n,q;
void init(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&val[i]);
		sm[i]=val[i];
	}
	int op,x,y;
	for(int i=1;i<=q;++i){
		scanf("%d%d%d",&op,&x,&y);
		switch(op){
			case 0:{
				split(x,y);
				printf("%d\n",sm[y]);
				break;
			}
			case 1:{
				link(x,y);
				break;
			}
			case 2:{
				cut(x,y);
				break;
			}
			case 3:{
				splay(x);
				val[x]=y;
				updt(x);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}