【刷题】洛谷 P3690 【模板】Link Cut 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。

输入输出格式

输入格式：

第1行两个整数，分别为n和m，代表点数和操作数。

第2行到第n+1行，每行一个整数，整数在［1，10^9］内，代表每个点的权值。

第n+2行到第n+m+1行，每行三个整数，分别代表操作类型和操作所需的量。

输出格式：

对于每一个0号操作，你须输出x到y的路径上点权的xor和。

输入输出样例

输入样例#1：

3 3

1

2

3

1 1 2

0 1 2

0 1 1

输出样例#1：

3

1

说明

数据范围： \(1 \leq N, M \leq 3 \cdot {10}^5\)

题解

看了那么久的博客，终于开始打LCT了，只不过现在还没有完全懂啊，模板几乎照抄，这种东西就背去吧

既然是模板题，就没什么好说的了，LCT维护就是链上的异或和，其它的就完全是基本操作

（如果你不知道LCT是什么或者没有学过／想学LCT，推荐一处 LCT总结+题单+洛谷P3690[模板]Link Cut Tree(动态树)(LCT,Splay)）

#include<bits/stdc++.h>

#define ll long long

#define db double

#define ld long double

#define lc(x) ch[x][0]

#define rc(x) ch[x][1]

const int MAXN=300000+10;

int n,m,A[MAXN];

struct LCT{

	int fa[MAXN],ch[MAXN][2],sum[MAXN],rev[MAXN];

	inline void init()

	{

		memset(fa,0,sizeof(fa));

		memset(ch,0,sizeof(ch));

		memset(sum,0,sizeof(sum));

		memset(rev,0,sizeof(rev));

	}

	inline bool nroot(int x)

	{

		return lc(fa[x])==x||rc(fa[x])==x;

	}

	inline void reverse(int x)

	{

		std::swap(lc(x),rc(x));

		rev[x]^=1;

	}

	inline void pushup(int x)

	{

		sum[x]=sum[lc(x)]^sum[rc(x)]^A[x];

	}

	inline void pushdown(int x)

	{

		if(rev[x])

		{

			if(lc(x))reverse(lc(x));

			if(rc(x))reverse(rc(x));

			rev[x]=0;

		}

	}

	inline void rotate(int x)

	{

	    int f=fa[x],p=fa[f],c=(rc(f)==x);

	    if(nroot(f))ch[p][ch[p][1]==f]=x;

	    fa[ch[f][c]=ch[x][c^1]]=f;

		fa[ch[x][c^1]=f]=x;

		fa[x]=p;

	    pushup(f);

		pushup(x);

	}

	inline void splay(int x)

	{

		std::stack<int> s;

		s.push(x);

		for(register int i=x;nroot(i);i=fa[i])s.push(fa[i]);

		while(!s.empty())pushdown(s.top()),s.pop();

		for(register int y=fa[x];nroot(x);rotate(x),y=fa[x])

			if(nroot(y))rotate((x==lc(y))==(y==lc(fa[y]))?y:x);

		pushup(x);

	}

	inline void access(int x)

	{

		for(register int y=0;x;x=fa[y=x])splay(x),rc(x)=y,pushup(x);

	}

	inline void makeroot(int x)

	{

		access(x);splay(x);reverse(x);

	}

	inline int findroot(int x)

	{

		access(x);splay(x);

		while(lc(x))pushdown(x),x=lc(x);

		return x;

	}

	inline void split(int x,int y)

	{

		makeroot(x);access(y);splay(y);

	}

	inline void link(int x,int y)

	{

		makeroot(x);

		if(findroot(y)!=x)fa[x]=y;

	}

	inline void cut(int x,int y)

	{

		makeroot(x);

		if(findroot(y)==x&&fa[x]==y&&!rc(x))fa[x]=lc(y)=0,pushup(y);

	}

};

LCT T;

template<typename T> inline void read(T &x)

{

	T data=0,w=1;

	char ch=0;

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

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

	x=data*w;

}

template<typename T> inline void write(T x,char c='\0')

{

	if(x<0)putchar('-'),x=-x;

	if(x>9)write(x/10);

	putchar(x%10+'0');

	if(c!='\0')putchar(c);

}

template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}

template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

int main()

{

	read(n);read(m);

	for(register int i=1;i<=n;++i)read(A[i]);

	T.init();

	while(m--)

	{

		int opt,x,y;

		read(opt);read(x);read(y);

		if(opt==0)T.split(x,y),write(T.sum[y],'\n');

		if(opt==1)T.link(x,y);

		if(opt==2)T.cut(x,y);

		if(opt==3)T.splay(x),A[x]=y;

	}

	return 0;

}

巴特西

【刷题】洛谷 P3690 【模板】Link Cut Tree （动态树）

题目背景

题目描述

输入输出格式

输入输出样例

说明

题解

最新文章

热门文章