BZOJ 3282 Tree

题目大意

给定N个点以及每个点的权值,要你处理接下来的M个操作.操作有4种.操作从0到3编号.点从1到N编号.

操作如下:

0. 后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和.保证x到y是联通的.
1. 后接两个整数(x,y),代表连接x和y,若x到y已经联通则无需连接.
2. 后接两个整数(x,y),代表删除边(x,y),不保证边(x,y)存在.
3. 后接两个整数(x,y),代表将点x上的权值变成y.

用LCT维护树上信息就可以了。

Splay()首先要从上到下做一通pushdown(),查询父亲的时候记得pushdown(),link()的时候记得pushup().

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

#define N 300010

int n,m,md,ix,iy,fa[N],c[2][N],v[N],t[N];
bool rev[N];

inline int RI()
{
	int ret=0;
	char tmp=getchar();
	while(tmp<'0'||tmp>'9') tmp=getchar();
	while(tmp>='0'&&tmp<='9') ret=ret*10+tmp-'0',tmp=getchar();
	return ret;
}

inline void pushup(int pos)
{
	v[pos]=v[c[0][pos]]^v[c[1][pos]]^t[pos];
}

inline void pushdown(int pos)
{
	if(rev[pos])
	{
		swap(c[0][c[0][pos]],c[1][c[0][pos]]);
		swap(c[0][c[1][pos]],c[1][c[1][pos]]);
		rev[c[0][pos]]^=1,rev[c[1][pos]]^=1;
		rev[pos]=false;
	}
}

inline bool isroot(int pos)
{
	return c[0][fa[pos]]!=pos&&c[1][fa[pos]]!=pos;
}

void init(int pos)
{
	if(!isroot(pos)) init(fa[pos]);
	pushdown(pos);
}

inline void rotate(int tx)
{
	int ty=fa[tx],tz=fa[ty],tl=(c[1][ty]==tx),tr=tl^1;
	if(!isroot(ty)) c[c[1][tz]==ty][tz]=tx;
	fa[tx]=tz,fa[ty]=tx;
	fa[c[tr][tx]]=ty,c[tl][ty]=c[tr][tx],c[tr][tx]=ty;
	pushup(ty),pushup(tx);
}

inline void splay(int tx)
{
	init(tx);
	while(!isroot(tx))
	{
		int ty=fa[tx],tz=fa[ty];
		if(!isroot(ty))
		{
			if((c[0][ty]==tx)^(c[0][tz]==ty)) rotate(tx);
			else rotate(ty);
		}
		rotate(tx);
	}
}

inline void access(int pos)
{
	int tmp=0;
	while(pos)
	{
		splay(pos);
		c[1][pos]=tmp;
		pushup(pos);
		tmp=pos,pos=fa[pos];
	}
}

inline void cgroot(int pos)
{
	access(pos),splay(pos);
	swap(c[0][pos],c[1][pos]);
	rev[pos]^=1;
}

inline void cut(int tx,int ty)
{
	cgroot(tx),access(ty),splay(ty);
	if(c[0][ty]==tx) c[0][ty]=fa[tx]=0,pushup(ty);
}

inline int lookfor(int pos)
{
	access(pos),splay(pos);
	while(c[0][pos]) pushdown(pos),pos=c[0][pos];
	return pos;
}

inline void link(int tx,int ty)
{
	if(lookfor(tx)!=lookfor(ty))
		cgroot(tx),fa[tx]=ty;
}

inline int query(int tx,int ty)
{
	cgroot(tx),access(ty),splay(ty);
	return v[ty];
}

inline void changev()
{
	splay(ix);
	v[ix]=v[ix]^t[ix]^iy;
	t[ix]=iy;
}

int main()
{
	n=RI(),m=RI();
	for(int i=1;i<=n;++i) scanf("%d",v+i),t[i]=v[i];
	while(m--)
	{
		md=RI(),ix=RI(),iy=RI();
		switch(md)
		{
			case 0: printf("%d\n",query(ix,iy));break;
			case 1: link(ix,iy);break;
			case 2: cut(ix,iy);break;
			case 3: changev();break;
		}
	}
	return 0;
}