Lvat_s Blog

Link-Cut Tree直接上……

但是因为智商原因2天才能理解+写会这个东西。

因为BZOJ爆了所以测不了。但是和hzwer的程序对拍了没拍出什么错误。。。在BZOJ上AC了

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m;

struct Node{
int v,ans,rev;
Node *ch[2],*fa;
Node(int val,Node *fat);
void Pushdown();
void Pushup();
}*root[300005],*Null;

Node::Node(int val=0,Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
v=ans=val;
rev=0;
}

void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0],ch[1]);
	rev=0;
}
}

void Node::Pushup(){
ans=v;
if(ch[0]!=Null)ans^=ch[0]->ans;
if(ch[1]!=Null)ans^=ch[1]->ans;
}

int Notroot(Node *x){
return (x->fa->ch[0]==x)||(x->fa->ch[1]==x);
}

void Prepare(Node *x){
if(Notroot(x))Prepare(x->fa);
x->Pushdown();
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y)){Rotate(x,y->ch[0]==x);}
	else {
		if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else {Rotate(x,1);Rotate(x,0);}
	}
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}
}

void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
}

void Link(Node *x,Node *y){
Makeroot(x);
x->fa=y;
}

void Cut(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
if(y->ch[0]==x){y->ch[0]=Null;x->fa=Null;}
}

Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}

Node *ToLct(int x){
return root[x];
}

int Xor(int x,int y){
Node *u=ToLct(x),*v=ToLct(y);
Makeroot(u);
Access(v);
Splay(v);
return v->ans;
}

void Add(int x,int y){
Node *u=ToLct(x),*v=ToLct(y);
Link(u,v);
}

void Delete(int x,int y){
Node *u=ToLct(x),*v=ToLct(y);
Cut(u,v);
}

void Change(int x,int y){
Node *u=ToLct(x);
Access(u);
Splay(u);
u->v=y;
u->Pushup();
}

Node *GetNull(){
Node *re=new Node(0,re);
re->v=re->ans=re->rev=0;
re->ch[0]=re->fa=re->ch[1]=re;
return re;
}

int main(){
freopen("3282.in","r",stdin);
freopen("3282.out","w",stdout);
scanf("%d %d",&n,&m);
Null=GetNull();
for(int i=1;i<=n;i++){
	int tp;
	scanf("%d",&tp);
	root[i]=new Node(tp,Null);
}
for(int i=1;i<=m;i++){
	int opt,x,y;
    scanf("%d %d %d",&opt,&x,&y);
    if(opt==0){printf("%d\n",Xor(x,y));}
    if(opt==1 && Find(ToLct(x))!=Find(ToLct(y)) && x!=y){Add(x,y);}
    if(opt==2 && Find(ToLct(x))==Find(ToLct(y)) && x!=y){Delete(x,y);}
    if(opt==3){Change(x,y);}
}
return 0;
}