正文 

当前位置： 首页 > 知识 > java教程

luogup3690模板linkcuttree（动态树）

lordxx lordxx     2022-12-03     191

关键词： 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#include <iomanip>
#pragma GCC optimize(2)
#define up(i,a,b)  for(int i=a;i<b;i++)
#define dw(i,a,b)  for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()

	char ch = getchar(); ll x = 0, f = 1;
	while (ch<‘0‘ || ch>‘9‘)  if (ch == ‘-‘)f = -1; ch = getchar(); 
	while (ch >= ‘0‘ && ch <= ‘9‘)  x = x * 10 + ch - ‘0‘; ch = getchar(); 
	return x * f;

typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 3e5 + 10;
int n, m;
struct node 
	int ch[2], fa, lazy, val;
tree[N];
int val[N];
int ident(int rt,int fa) 
	return tree[fa].ch[1] == rt;

void connect(int rt, int fa,int son)

	tree[rt].fa = fa;
	tree[fa].ch[son] = rt;

bool isroot(int rt)

	int f = tree[rt].fa;
	return tree[f].ch[1] != rt && tree[f].ch[0] != rt;

void pushup(int rt) 
	int ls = tree[rt].ch[0];
	int rs = tree[rt].ch[1];
	tree[rt].val = tree[ls].val^tree[rs].val ^ val[rt];

void rev(int x)

	swap(tree[x].ch[0], tree[x].ch[1]);
	tree[x].lazy ^= 1;

void pushdown(int rt)

	if (tree[rt].lazy)
	
		if (tree[rt].ch[0])rev(tree[rt].ch[0]);
		if (tree[rt].ch[1])rev(tree[rt].ch[1]);
		tree[rt].lazy = 0;
	

void pushall(int rt)

	if (!isroot(rt))pushall(tree[rt].fa);
	pushdown(rt);

void rotate(int rt)

	int f = tree[rt].fa; int ff = tree[f].fa; int k = ident(rt, f);
	connect(tree[rt].ch[k ^ 1], f, k);
	tree[rt].fa = ff;
	if (!isroot(f))tree[ff].ch[ident(f, ff)] = rt;
	connect(f, rt, k ^ 1);
	pushup(f); pushup(rt);

void splay(int x)

	pushall(x);
	while (!isroot(x))
	
		int f = tree[x].fa; int ff = tree[f].fa;
		if (!isroot(f))
			ident(f, ff) ^ ident(x, f) ? rotate(x) : rotate(f);
		rotate(x);
	

void access(int x)

	for (int y = 0; x; x = tree[x].fa)
	
		splay(x);
		tree[x].ch[1] = y;
		pushup(x);        
		y = x;
	

void makeroot(int x)

	access(x); splay(x); rev(x);

int findroot(int x)

	access(x); splay(x);
	while (tree[x].ch[0]) 
		pushdown(x);
		x = tree[x].ch[0];
	
	splay(x);
	return x;

void link(int x,int y)

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

void cut(int x, int y)

	makeroot(x);
	if (findroot(y) != x || tree[y].fa != x || tree[y].ch[0])return;
	tree[y].fa = tree[x].ch[1] = 0;
	pushup(x);

void split(int x, int y)

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

int main()

#ifdef local
	freopen("D:++P3690_9.in", "r", stdin);
	freopen("D:++P3369_2.out", "w", stdout);
#endif // 

	n = read(), m = read();
	upd(i, 1, n)tree[i].val = read(), val[i] = tree[i].val;
	int op, xx, yy;
	while (m--)
	
		op = read();
		xx = read(), yy = read();
		if (op == 0)
		
			split(xx, yy);
			printf("%d
", tree[yy].val);
		
		else if (op == 1)
		
			link(xx, yy);
		
		else if (op == 2)
		
			cut(xx, yy);
		
		else if (op == 3)
		
			splay(xx);
			val[xx] = yy;
			pushup(xx);
		
	
	return 0;

luogup3690模板linkcuttree（动态树）[lct]

题目背景动态树题目描述给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证... 查看详情

ac日记——模板linkcuttree洛谷p3690

【模板】LinkCutTree 思路：　　LCT模板； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn300005intn,m,val[maxn];inttop,ch[maxn][2],f[maxn],xr[maxn],q[maxn],rev[maxn];inlinevoidin(int&now 查看详情

luogu3690模板linkcuttree（动态树）

题目luogu3690硫硼作者想提醒大家，WA了TLE了RE了的，也许只是主函数写错了代码#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstdlib>#include<cstring>usingnamespacestd 查看详情

luogu3690模板linkcuttree（动态树）

参考there和there#include<iostream>#include<cstdio>usingnamespacestd;intn,m,val[300005],ch[300005][2],sum[300005],fa[300005],uu,vv,opt;intrev[300005];voidpushDown(intx)if(rev[x])swap(ch[x][0 查看详情

洛谷3690：模板linkcuttree——题解(代码片段)

https://www.luogu.org/problemnew/show/P3690给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：... 查看详情

p3690linkcuttree(动态树)

干脆整个LCT模板吧。缺个链上修改和子树操作，链上修改的话join(u,v)然后把vsplay到树根再打个标记就好。至于子树操作...以后有空的话再学(咕咕咕警告)1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintN=1e5+10;5intn,m,a[N],X... 查看详情

p3690模板linkcuttree（动态树）(代码片段)

哇，做梦也没想到我居然能写LCT题意：给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通... 查看详情

洛谷p3690模板linkcuttree（lct）(代码片段)

题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两... 查看详情

刷题洛谷p3690模板linkcuttree（动态树）(代码片段)

题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两... 查看详情

p3690模板linkcuttree（动态树）(代码片段)

P3690【模板】LinkCutTree（动态树）注意：不要把$fa[x]$和$nrt(x)$混在一起！#include<cstdio>voidswap(int&a,int&b)a^=b^=a^=b;#defineN300005intn,m,s[N],v[N],ch[2][N],fa[N],rev[N];#definelcch[0][x]#definercch[1][x]boolnrt(intx)returnch[0][fa[x]]==x||ch[1][fa[x]]==x;voidu... 查看详情

p3690模板linkcuttree（动态树）(代码片段)

LCTLCT即Link-Cut-Tree维护一个森林，支持很多操作，比如：维护链上信息（min，max，sum，xor。。。。。。）换根动态维护联通性维护子树信息概念虚边：连接儿子与父亲，儿子记录父亲，父亲不记录儿子（父不认子）实边：父子互... 查看详情

[p3690]linkcuttree(代码片段)

Description:给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两个整数(x，y)，代... 查看详情

数据结构专题-学习笔记：linkcuttree动态树

1.前言LinkCutTree动态树，简称LCT，是一种维护动态森林的数据结构。前置知识：Splay。2.LCT例题：P3690【模板】动态树（LinkCutTree）2.1实链剖分实链剖分也是一种对树的剖分方式，类似于重链剖分和长链剖分，其将一棵树上的边，随... 查看详情

luogup3690列队(代码片段)

https://www.luogu.org/problemnew/show/P3960作为一个初二蒟蒻要考提高组，先做一下17年的题目我们发现进行一次操作相当于把第x行的第y个弹出记为a，其余向左移=splay中弹出第y个把第m列的第x个弹出记为b，其余向上移=splay中弹出第x个把b... 查看详情

模板linkcuttree（动态树）

题目描述给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的... 查看详情

[模板]linkcuttree(代码片段)

...：后接两个整数(x，y)，代表将点x上的权值变成y。Solution(LinkCutTree)模板题(findroot)后要(Splay)到根？不然复杂度不保证？？？在洛谷上实测(535ms)，还算比较快吧函数变量名奇异+神仙缩行(ightarrow)还是别看了Code?//2019.1.2618:41-22:54#inclu... 查看详情

luogup3809模板后缀排序

二次联通门:luoguP3809【模板】后缀排序     /*luoguP3809【模板】后缀排序后缀数组sa表示排名为i的是第几个后缀求出sa数组后输出即可*/#include<cstdio>#include<cstring>#defineMax1000008voidread(int&now){registerch 查看详情

lct(linkcuttree)动态树(代码片段)

模板参考：https://blog.csdn.net/saramanda/article/details/55253627几个知识点：1、LCT中用Splay维护链，这些Splay叫做“辅助树“。辅助树以它上面每个节点的深度为关键字维护，就是辅助树中每个节点左儿子的深度小于当前节点的深度... 查看详情