题目描述
给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。
０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。
１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。
２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。
３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。
输入输出格式
输入格式：
第１行两个整数，分别为Ｎ和Ｍ，代表点数和操作数。
第２行到第Ｎ＋１行，每行一个整数，整数在［１，１０＾９］内，代表每个点的权值。
第Ｎ＋２行到第Ｎ＋Ｍ＋１行，每行三个整数，分别代表操作类型和操作所需的量。
输出格式：
对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。
输入输出样例
说明
数据范围： 1≤N,M≤3⋅105
算法原理提供可靠网址：
这道题用到的技巧：
找根：$makeroot(o)$后一直往左走。最后一个节点就是根。（理由：由于$LCT$中$splay$的性质：按深度作为键值）；
判断是否之间有边：再$cut$之前，判断根的左儿子是否是另外一个点。（理由：若存在边，则包含这条边的$splay$只有两个节点）。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int xr[],ch[][],val[],pre[],n,m;
bool isrt[],rev[];
void pushup(int o)
{
if (!o) return;
xr[o]=xr[ch[o][]]^xr[ch[o][]]^val[o];
}
void pushdown(int o)
{
if (!o) return;
if (rev[o])
{
int ls=ch[o][],rs=ch[o][];
if (ls)
{
rev[ls]^=;
swap(ch[ls][],ch[ls][]);
}
if (rs)
{
rev[rs]^=;
swap(ch[rs][],ch[rs][]);
}
rev[o]=;
}
}
void push(int o)
{
if (isrt[o]==)
push(pre[o]);
pushdown(o);
}
void rotate(int o,bool kind)
{
int p=pre[o];
ch[p][!kind]=ch[o][kind];pre[ch[o][kind]]=p;
if (isrt[p]) isrt[o]=,isrt[p]=;
else ch[pre[p]][ch[pre[p]][]==p]=o;
pre[o]=pre[p];
ch[o][kind]=p;pre[p]=o;
pushup(p);pushup(o);
}
void splay(int o)
{
push(o);
while (isrt[o]==)
{
if (isrt[pre[o]])
rotate(o,ch[pre[o]][]==o);
else
{
int p=pre[o],kind=ch[pre[p]][]==p;
if (ch[p][kind]==o)
rotate(o,!kind),rotate(o,kind);
else rotate(p,kind),rotate(o,kind);
}
}
}
void access(int o)
{
int y=;
while (o)
{
splay(o);
//xr[o]^=xr[ch[o][1]];
isrt[ch[o][]]=;isrt[ch[o][]=y]=;
pushup(o);
o=pre[y=o];
}
}
void makeroot(int o)
{
access(o);
splay(o);
rev[o]^=;
swap(ch[o][],ch[o][]);
}
int find(int o)
{
makeroot(o);
access(o);splay(o);
while (ch[o][])
{
o=ch[o][];
}
return o;
}
void link(int x,int y)
{
makeroot(x);
pre[x]=y;
}
void cut(int x,int y)
{
makeroot(x);access(y);splay(y);
if (ch[y][]!=x) return;
pre[x]=;
ch[y][]=;
isrt[x]=;
pushup(y);
}
int main()
{int i,c,x,y;
cin>>n>>m;
for (i=;i<=n;i++)
{
scanf("%d",&val[i]);
xr[i]=val[i];isrt[i]=;
}
for (i=;i<=m;i++)
{
scanf("%d%d%d",&c,&x,&y);
if (c==)
{
makeroot(y);
access(x);
splay(x);
printf("%d\n",xr[x]);
}
else if (c==)
{
int p=find(x),q=find(y);
if (p!=q) link(x,y);
}
else if (c==)
{
cut(x,y);
}
else if (c==)
{
val[x]=y;
makeroot(x);
pushup(x);
}
}
}