code

当然，一贯不要脸的我，明明自己的代码是看的xzy的，还是附上了自己的代码

PS:不得不承认，set是个好东西啊
#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iomanip>

#include<algorithm>

#include<ctime>

#include<queue>

#include<stack>

#include<vector>

#include<set>

#define rg register

#define il inline

#define lst long long

#define ldb long double

#define N 300050

using namespace std;

const int Inf=1e9;

il int read()

{

	rg int s=0,m=0;rg char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}

	while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();

	return m?-s:s;

}

int n,m,top;

int st[N];

set<int> link[N];

struct SPLAY{int fa,v,sum,tag,ch[2];}ljl[N];

il void Pushup(rg int x){ljl[x].sum=ljl[ljl[x].ch[0]].sum^ljl[ljl[x].ch[1]].sum^ljl[x].v;}

il void Reverse(rg int x){swap(ljl[x].ch[0],ljl[x].ch[1]);ljl[x].tag^=1;}

il void Pushdown(rg int x)

{

	if(ljl[x].tag)

	{

		if(ljl[x].ch[0])Reverse(ljl[x].ch[0]);

		if(ljl[x].ch[1])Reverse(ljl[x].ch[1]);

		ljl[x].tag=0;

	}

}

il bool Isroot(rg int x){return ((ljl[ljl[x].fa].ch[0]!=x)&&(ljl[ljl[x].fa].ch[1]!=x));}

il void Rotate(rg int x)

{

	rg int y=ljl[x].fa,z=ljl[y].fa;

	rg int k=ljl[y].ch[1]==x;

	if(!Isroot(y))ljl[z].ch[ljl[z].ch[1]==y]=x;

	ljl[x].fa=z;

	ljl[y].ch[k]=ljl[x].ch[k^1];

	ljl[ljl[x].ch[k^1]].fa=y;

	ljl[x].ch[k^1]=y;

	ljl[y].fa=x;

	Pushup(y);

}

il void Splay(rg int x)

{

	st[++top]=x;

	for(rg int i=x;!Isroot(i);i=ljl[i].fa)st[++top]=ljl[i].fa;

	while(top)Pushdown(st[top--]);

	while(!Isroot(x))

	{

		rg int y=ljl[x].fa,z=ljl[y].fa;

		if(!Isroot(y))(ljl[y].ch[0]==x)^(ljl[z].ch[0]==y)?Rotate(x):Rotate(y);

		Rotate(x);

	}

	Pushup(x);

}

il void Access(rg int x)

{

	for(rg int y=0;x;y=x,x=ljl[x].fa)

		Splay(x),ljl[x].ch[1]=y,Pushup(x);

}

il void Make_root(rg int x){Access(x),Splay(x),Reverse(x);}

il int Find_root(rg int x)

{

	Access(x),Splay(x);

	while(ljl[x].ch[0])x=ljl[x].ch[0];

	return x;

}

il void Split(rg int x,rg int y){Make_root(x),Access(y),Splay(y);}

il void Link(rg int x,rg int y)

{

	Make_root(x),ljl[x].fa=y;

	link[x].insert(y),link[y].insert(x);

}

il void Cut(rg int x,rg int y)

{

	Split(x,y);

	ljl[x].fa=ljl[y].ch[0]=0;

	link[x].erase(y),link[y].erase(x);

}

int main()

{

	freopen("s.in","r",stdin);

	n=read(),m=read();

	for(rg int i=1;i<=n;++i)

		ljl[i].sum=ljl[i].v=read();

	for(rg int i=1;i<=m;++i)

	{

		rg int opt=read(),x=read(),y=read();

		if(opt==0)//x--y异或和

		{

			Split(x,y);//抠出路径，此时这条路径的异或和存在SPLAY根节点y中

			printf("%d\n",ljl[y].sum);//直接输出sum[y]就ok

		}

		if(opt==1)//连接x--y

			if(Find_root(x)^Find_root(y))Link(x,y);//如果不是同一个联通块里就连边

		if(opt==2)//删除x--y

			if(link[x].find(y)!=link[x].end())Cut(x,y);//如果x所连的边中找到了y(没有找到set尾部)就删边

		if(opt==3)//把x的权值改为y

		{

			Access(x),Splay(x);//把x抠出来并放到SPLAY的根节点(不会影响到其他元素的sum)

			ljl[x].v=y,Pushup(x);//直接修改就行，顺便更新一下自己

		}

	}

	return 0;

}
巴特西

Link-Cut-Tree学习(LCT)

Link-Cut-Tree学习(LCT)

code

最新文章

热门文章
