50行LCT模板

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define gt getchar()
inline int in()
{
	int k=0;char ch=gt;bool p=1;
	while(ch<'-')ch=gt;if(ch=='-')p=0,ch=gt;
	while(ch>'-')k=k*10+ch-'0',ch=gt;
	return p?k:-k;
}
const int N=3e5+5;
int ch[N][2],fa[N],sum[N],val[N],lz[N];
#define lc ch[x][0]
#define rc ch[x][1]
inline int nrt(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
inline int pd(int x){return ch[fa[x]][1]==x;}
inline void up(int x){sum[x]=val[x]^sum[lc]^sum[rc];}
inline void rever(int x){lz[x]^=1;std::swap(lc,rc);}
inline void down(int x){if(lz[x]){if(lc)rever(lc);if(rc)rever(rc);lz[x]=0;}}
inline void rot(int x)
{
	int y=fa[x],z=fa[y],d=pd(x),w=ch[x][d^1];
	if(nrt(y))ch[z][pd(y)]=x;ch[x][d^1]=y,ch[y][d]=w;
	if(w)fa[w]=y;fa[x]=z,fa[y]=x;up(y);
}
inline void splay(int x)
{
	static int y,z,st[N];y=x,z=0;st[++z]=y;
	while(nrt(y))y=fa[y],st[++z]=y;while(z)down(st[z--]);
	for(y=fa[x];nrt(x);rot(x),y=fa[x])if(nrt(y))rot((pd(y)^pd(x))?x:y);up(x);
}
inline void access(int x){for(int y=0;x;rc=y,up(x),x=fa[y=x])splay(x);}
inline void makert(int x){access(x),splay(x),rever(x);}
inline void split(int x,int y){makert(x),access(y),splay(y);}
inline int findrt(int x){access(x),splay(x),down(x);while(lc)x=lc,down(x);return splay(x),x;}
inline void link(int x,int y){makert(x);if(findrt(y)!=x)fa[x]=y,up(y);}
inline void cut(int x,int y){makert(x);if(findrt(y)==x&&fa[y]==x&&!ch[y][0])rc=fa[y]=0,up(x);}
int main()
{
	int n=in(),m=in();
	for(int i=1;i<=n;++i)sum[i]=val[i]=in();
	for(int i=1;i<=m;++i)
	{
		int op=in(),x=in(),y=in();
		if(op==0)split(x,y),printf("%d\n",sum[y]);
		if(op==1)link(x,y);
		if(op==2)cut(x,y);
		if(op==3)val[x]=y,splay(x);
	}
	return 0;
}