Link-Cut-Tree学习(LCT)
真不敢想象我居然学会LCT了，但是我仍然不想写一篇博客来梳理
我怕一梳理自己又不懂了
但是作为一名朴实沉毅的cjoier，我决定小小的梳理一下，并不打算很精致......
我这样说也是有资本的，下面推荐两个教会我LCT的博客
FlashHu的总结+题单+升级
xzy的题单+好板子
其实贴上这两个博客也就没我什么事了，所以，溜了溜了
以后我想复习了直接就点开QwQ
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
",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;
}