思路：
LCT模板；
代码：
#include <bits/stdc++.h>
using namespace std;
#define maxn 300005
int n,m,val[maxn];
int top,ch[maxn][],f[maxn],xr[maxn],q[maxn],rev[maxn];
inline void in(int &now)
{
int if_z=;now=;
char Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
}
inline void updata(int now)
{
xr[now]=xr[ch[now][]]^xr[ch[now][]]^val[now];
}
inline void downdata(int now)
{
int l=ch[now][],r=ch[now][];
if(rev[now])
{
rev[l]^=,rev[r]^=,rev[now]^=;
swap(ch[now][],ch[now][]);
}
}
inline bool isroot(int now)
{
return ch[f[now]][]!=now&&ch[f[now]][]!=now;
}
inline void rotate(int now)
{
int fa=f[now],ffa=f[fa],l,r;
if(ch[fa][]==now) l=;else l=;r=l^;
if(!isroot(fa))
{
if(ch[ffa][]==fa) ch[ffa][]=now;
else ch[ffa][]=now;
}
f[now]=ffa,f[fa]=now,f[ch[now][r]]=fa;
ch[fa][l]=ch[now][r],ch[now][r]=fa;
updata(fa),updata(now);
}
inline void splay(int now)
{
top=,q[top]=now;
for(int i=now;!isroot(i);i=f[i]) q[++top]=f[i];
for(int i=top;i;i--) downdata(q[i]);
while(!isroot(now))
{
int fa=f[now],ffa=f[fa];
if(!isroot(fa))
{
if((ch[fa][]==now)^(ch[ffa][]==fa)) rotate(now);
else rotate(fa);
}
rotate(now);
}
}
void access(int now)
{
for(int t=;now;t=now,now=f[now])
{
splay(now);
ch[now][]=t;
updata(now);
}
}
void makeroot(int now)
{
access(now);
splay(now);
rev[now]^=;
}
int find(int now)
{
access(now);
splay(now);
while(ch[now][]) now=ch[now][];
return now;
}
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
}
void cut(int x,int y)
{
split(x,y);
if(ch[y][]==x) ch[y][]=,f[x]=;
}
void link(int x,int y)
{
makeroot(x);
f[x]=y;
}
int main()
{
in(n),in(m);int op,x,y,xx,yy;
for(int i=;i<=n;i++) in(val[i]),xr[i]=val[i];
while(m--)
{
in(op);
if(op==)
{
in(x),in(y),split(x,y);
printf("%d\n",xr[y]);
}
if(op==)
{
in(x),in(y),xx=find(x),yy=find(y);
if(xx!=yy) link(x,y);
}
if(op==)
{
in(x),in(y),xx=find(x),yy=find(y);
if(xx==yy) cut(x,y);
}
if(op==)
{
in(x),in(y);
access(x);
splay(x);
val[x]=y;
updata(x);
}
}
}