【模板】LCT

核心思想：

动态维护一个森林。支持删边和加边，查询链信息和连通块信息等很多操作。

由若干棵$Splay$组成，每棵$Splay$维护一条链，以深度作为关键字。

也就是说$Splay$的中序遍历相当于从上到下遍历这条链。

$Splay$中的边是实边，将两个$Splay$相连的边是虚边。

实边的父亲有它这个儿子（双向关系），虚边的父亲没有它这个儿子（单向关系）。

组成$LCT$的基础操作：（以下均认为$LCT$中只有一棵树）

$access(x)$：打通根到$x$的路径，使一棵包含且仅包含根到$x$这条链上点的$Splay$出现。

实现方法：

1.$splay(x)$：将$x$转到当前$Splay$的根。（此时$x$是该$Splay$中最深的点，没有右儿子）

2.$c[x][1]=y$：将$x$的右儿子设为刚才操作的$Splay$的根。

3.$x=f[x]$：继续操作$x$在原树中的父亲，若$x$已经为根则退出。

$makeroot(x)$：使$x$成为根。

实现方法：

1.$access(x)$。

2.$splay(x)$。

3.翻转整棵$Splay$。

为什么不能只翻转$x$的左右儿子：一个链提末端点当根之后整个链的深度顺序全部翻转。

如：$1-2-3$翻转后为$3-2-1$而不是$3-1-2$。

$findroot(x)$：找$x$所在原树的根。

实现方法：

1.$access(x)$。

2.$splay(x)$。

3.在$Splay$上一直往左走，最终走到答案点$y$。

3.$splay(y)$。

$split(x,y)$：拉出路径$(x,y)$成为一个$Splay$，并令$x$为原树的根。

实现方法：

1.$makeroot(x)$。

2.$access(y)$。

$link(x,y)$：连一条边$(x,y)$。

实现方法：

1.$makeroot(x)$。

2.若$findroot(y)\neq x$则$f[x]=y$。

$cut(x,y)$：断开边$(x,y)$。

实现方法：

1.若$findroot(x)=findroot(y)$则$split(x,y)$。

2.若$f[y]=x$且$c[y][0]=0$则$f[y]=c[x][1]=0$。

代码：

#include<bits/stdc++.h>

#define maxn 100005

#define maxm 500005

#define inf 0x7fffffff

#define ll long long

using namespace std;

int N,M,rc,A[maxn],s[maxn],st[maxn];

int r[maxn],c[maxn][],f[maxn];

inline int read(){

    int x=,f=; char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

inline bool nroot(int x){return c[f[x]][]==x||c[f[x]][]==x;}

inline void pushr(int x){swap(c[x][],c[x][]),r[x]^=;}

inline void pushup(int x){s[x]=s[c[x][]]^s[c[x][]]^A[x];}

inline void pushdown(int x){

    if(r[x]){

        if(c[x][]) pushr(c[x][]);

        if(c[x][]) pushr(c[x][]);

        r[x]=;

    }

}

inline void rotate(int x){

    int y=f[x],z=f[y],k=(c[y][]==x),w=c[x][!k];

    if(nroot(y)) c[z][c[z][]==y]=x;

    c[x][!k]=y,c[y][k]=w;

    if(w) f[w]=y;

    f[y]=x,f[x]=z;

    pushup(y);

}

inline void splay(int x){

    int y=x,z=; st[++z]=y;

    while(nroot(y)) st[++z]=y=f[y];

    while(z) pushdown(st[z--]);

    while(nroot(x)){

        y=f[x],z=f[y];

        if(nroot(y)) rotate(((c[y][]==x)^(c[z][]==y))?x:y);

        rotate(x);

    }

    pushup(x);

}

inline void access(int x){for(int y=;x;x=f[y=x]) splay(x),c[x][]=y,pushup(x);}

inline void makeroot(int x){access(x),splay(x),pushr(x);}

inline void split(int x,int y){makeroot(x),access(y),splay(y);}

inline int findroot(int x){

    access(x),splay(x);

    while(c[x][]) pushdown(x),x=c[x][];

    splay(x); return x;

}

inline void link(int x,int y){makeroot(x);if(findroot(y)!=x) f[x]=y;}

inline void cut(int x,int y){makeroot(x);if(findroot(y)==x && f[y]==x && !c[y][])f[y]=c[x][]=,pushup(x);}

int main(){

    N=read(),M=read();

    for(int i=;i<=N;i++) A[i]=read();

    while(M--){

        int op=read(),x=read(),y=read();

        if(op==) split(x,y),printf("%d\n",s[y]);

        if(op==) link(x,y);

        if(op==) cut(x,y);

        if(op==) splay(x),A[x]=y;

    }

    return ;

}

LCT

巴特西

【模板】LCT

最新文章

热门文章