震惊!新闻工作者助力大常数代码!

#include<algorithm>
#include<cstdio>
#define MaxN 300500
using namespace std;
inline int read()
{
  register int X=0;
  register char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
int n,m;
struct Splay_Node
{int l,r,f,x,s;
 bool tag;
 inline void ladd()
 {swap(l,r);tag^=1;}
}a[MaxN];
inline void up(int num)
{a[num].s=a[a[num].l].s^a[a[num].r].s^a[num].x;}
inline void ladd(int num)
{
  if (!a[num].tag)return ;
  a[a[num].l].ladd();
  a[a[num].r].ladd();
  a[num].tag=0;
}
inline bool nrt(int num)
{return a[a[num].f].l==num||a[a[num].f].r==num;}
inline void rotate(int num)
{
  int fa=a[num].f,gf=a[fa].f;
  ladd(fa);ladd(num);
  a[fa].f=num;
  a[num].f=gf;
  if (a[gf].l==fa)a[gf].l=num;
  if (a[gf].r==fa)a[gf].r=num;
  //记住一定要写成两个if,不然会出现0有儿子的情况 
  if (a[fa].l==num){
  	a[fa].l=a[num].r;
  	a[a[num].r].f=fa;
    a[num].r=fa;
  }else {
  	a[fa].r=a[num].l;
  	a[a[num].l].f=fa;
    a[num].l=fa;
  }up(fa);up(num);
}
void splay(int x)
{
  int y,z;
  ladd(x);//要先ladd 
  while(nrt(x)){
  	y=a[x].f;z=a[y].f;
  	if (nrt(y))
	  rotate((a[y].l==x)^(a[z].l==y)?x:y);
	rotate(x);
  }
}
void access(int x)
{
  for (int y=0;x;x=a[y=x].f){
  	splay(x);
  	//这句话把可能的那条重链切成了两部分
  	a[x].r=y;
	//a[x].r原先的那部分被切断,替换为y 
  	up(x);
  }
}
void makert(int x)
{
  access(x);splay(x);
  a[x].ladd();
  //整条路径反转 
} 
int findrt(int x)
{
  access(x);splay(x);ladd(x);
  while(a[x].l){x=a[x].l;ladd(x);}
  //寻找深度最浅的(别忘了ladd) 
  return x;
}
void link(int x,int y)
{
  makert(x);
  if (findrt(y)==x)return ;
  a[x].f=y;
}//认父不认子,可以有超过两个的"干儿子" 
void spilt(int x,int y)
{makert(x);access(y);splay(y);}
void cut(int x,int y)
{
  spilt(x,y);
  if (a[y].l!=x||a[x].l!=a[x].r)return ;
  //x可能会凑巧是左儿子,所以还要判断x是否没儿子 
  //此时x就在y的左儿子
  a[y].l=a[x].f=0;
  up(y);
}
int main()
{
  scanf("%d%d",&n,&m);
  for (int i=1;i<=n;i++)a[i].x=read();
  for (int i=1,ord,x,y;i<=m;i++){
    ord=read();x=read();y=read();
    if (ord==0){
      spilt(x,y);
      printf("%d\n",a[y].s);
	}if (ord==1)link(x,y);
    if (ord==2)cut(x,y);
    if (ord==3){
	  splay(x);
	  a[x].x=y;up(x);
	}
  }return 0;
}