LCT模板（学习笔记）（洛谷3690）（加边，删边，修改点权）
2024-10-14 09:16:52
最近学习了一波LCT qwq
强势安利Flashhu的博客！！！！！
真的特别详细（可惜我不会弄链接）
如果有想要学习\(LCT\)的同学，可以直接看他的博客
我这里就简单写一点自己的体会啊。
\(LCT\)大致上就是一个支持加边，删边，维护子树信息，路径修改，维护路径信息的一个数据结构
本质上LCT是一个实虚链划分
代码的话，主要是分为几个部分
首先是判断这个点是不是根 和 其儿子关系，也就是\(notroot\)和\(son\)函数
int son(int x)
{
if (ch[fa[x]][0]==x)
return 0;
else return 1;
}
bool notroot(int x)
{
return (ch[fa[x]][0]==x) || (ch[fa[x]][1]==x);
}
这块还是比较好理解的。
下面就是和平衡树\(splay\)很接近的两个操作了，\(rotate\)和\(splay\)
需要注意的是，这里的\(rotate\)需要判断\(y\)是不是\(root\)，而且\(splay\)的时候，需要先下放一些修改标记（按照从上到下的顺序下放）
void rotate(int x)
{
int y=fa[x],z=fa[y];
int b=son(x),c=son(y);
if(notroot(y)) ch[z][c]=x;
fa[x]=z;
ch[y][b]=ch[x][!b];
fa[ch[x][!b]]=y;
ch[x][!b]=y;
fa[y]=x;
update(y);
update(x);
//cout<<1<<endl;
}
void splay(int x)
{
int y=x,cnt=0;
st[++cnt]=y;
while(notroot(y)){y=fa[y];st[++cnt]=y;}
while (cnt) pushdown(st[cnt--]);
while (notroot(x))
{
int y=fa[x],z=fa[y];
int b=son(x),c=son(y);
if (!notroot(y)) rotate(x);
else
//if (notroot(y))
{
if (b==c)
{
rotate(y);
rotate(x);
}
else
{
rotate(x);
rotate(x);
}
}
//cout<<1<<endl;
}
update(x);
}
下面就是\(LCT\)的核心操作\(access\)
\(access(x)\)表示将根到x的路径都打通，也就是弄到同一个\(splay\)里面，具体的话，就是每次每次转到splay的顶部，然后连边，顺便\(update\)
void access(int x)
{
for (int y=0;x;y=x,x=fa[x])
{
splay(x);
ch[x][1]=y;
update(x);
}
}
其他操作就不在这里体现了
QWQ
那么回归这个题，其实如果了解了\(LCT\)的相关操作话，这就是一个LCT的模板题
所以直接上代码了
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 1e6+1e2;
int fa[maxn],ch[maxn][3];
int rev[maxn],sum[maxn];
int n,m;
int val[maxn];
int st[maxn];
int son(int x)
{
if (ch[fa[x]][0]==x)
return 0;
else return 1;
}
bool notroot(int x)
{
return (ch[fa[x]][0]==x) || (ch[fa[x]][1]==x);
}
void update(int x)
{
sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^val[x];
}
void reverse(int x)
{
swap(ch[x][0],ch[x][1]);
rev[x]^=1;
}
void pushdown(int x)
{
if (rev[x])
{
if (ch[x][0]) reverse(ch[x][0]);
if (ch[x][1]) reverse(ch[x][1]);
rev[x]=0;
}
}
void rotate(int x)
{
int y=fa[x],z=fa[y];
int b=son(x),c=son(y);
if(notroot(y)) ch[z][c]=x;
fa[x]=z;
ch[y][b]=ch[x][!b];
fa[ch[x][!b]]=y;
ch[x][!b]=y;
fa[y]=x;
update(y);
update(x);
//cout<<1<<endl;
}
void splay(int x)
{
int y=x,cnt=0;
st[++cnt]=y;
while(notroot(y)){y=fa[y];st[++cnt]=y;}
while (cnt) pushdown(st[cnt--]);
while (notroot(x))
{
int y=fa[x],z=fa[y];
int b=son(x),c=son(y);
if (!notroot(y)) rotate(x);
else
//if (notroot(y))
{
if (b==c)
{
rotate(y);
rotate(x);
}
else
{
rotate(x);
rotate(x);
}
}
//cout<<1<<endl;
}
update(x);
}
void access(int x)
{
for (int y=0;x;y=x,x=fa[x])
{
splay(x);
ch[x][1]=y;
update(x);
}
}
void makeroot(int x)
{
access(x);
//splay(x);
reverse(x);
}
int findroot(int x)
{
access(x);
splay(x);
while (ch[x][0])
{
pushdown(x);
x=ch[x][0];
}
//splay(x);
return x;
}
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
}
void link(int x,int y)
{
makeroot(x);
if (findroot(y)!=x) fa[x]=y;
}
void cut(int x,int y)
{
split(x,y);
if (ch[x][0] || ch[x][1] ||fa[x]!=y || ch[y][son(x)^1]) return;
fa[x]=ch[y][0]=0;
}
int main()
{
n=read(),m=read();
for (int i=1;i<=n;i++) val[i]=read();
for (int i=1;i<=m;i++)
{
int opt=read(),x=read(),y=read();
if(opt==0)
{
split(x,y);
printf("%d\n",sum[y]);
}
if(opt==1)
{
link(x,y);
}
if (opt==2)
{
cut(x,y);
}
if (opt==3)
{
splay(x);
val[x]=y;
}
}
return 0;
}
最新文章
- makefile基础（GNU）
- JS数组的forEach方法(兼容所有浏览器)
- 对于cocos2d-x lua的防护措施
- OC中控制台日志打印
- mvc与mvvm
- js的dom操作和函数
- WdatePicker时间插件
- JAVA WEB之Spring4.x JdbcTemplate
- docker进阶-初探Docker-compose
- cocoaPods安装爬坑总结
- ThreadPoolExecutor使用
- Java泛型相关总结（上）
- git使用之后悔药
- File类_删除一个带内容的目录_练习
- js捕获错误
- 风控3—iv算法详细解释
- delphi const的用法
- 2017 先知创新大会：有 ZHI 而来
- 你应该抓紧学习Python，它是开发Web应用最强大的语言
- 通过JS实现HTML的转义与反转义