Link-Cut-Tree学习(LCT)

数据结构——LCT
真不敢想象我居然学会LCT了，但是我仍然不想写一篇博客来梳理
我怕一梳理自己又不懂了
但是作为一名朴实沉毅的cjoier，我决定小小的梳理一下，并不打算很精致......
我这样说也是有资本的，下面推荐两个教会我LCT的博客
FlashHu的LCT总结
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\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;
}