省选复习 - LCT 笔记

LCT 笔记

最近在复习学过的省选算法，发现以前学的太不扎实了，太逊了，有必要做笔记整理一下

LCT 笔记

主要功能

在线维护树的加边和删边，以及树相关信息

复杂度只有一个 \(\log\)，乘以维护信息的复杂度（一般是 \(O(1)\)）

和其它数据结构的比较

逊的：

并查集+线段树分治：只能离线，而且不好维护树上的信息，倾向于维护联通块
轻重链剖分：缺少加边和删边的功能，而且多一个 \(\log\) 的复杂度
动态插入倍增：逊，只能加入一个点
树分块：难以实现加边和删边（也可能是我不会），而且复杂度是根号的

老大哥：

top tree ，yyds （我不会qaq

思想

考虑对轻重链剖分进行魔改

轻重剖分是怎么剖的？一开始预处理出 \(size\)，钦点 \(size\) 最大的是重儿子。

那么如果要支持加边和删边，每次重构显然不现实。

于是想到，也许不一定非要找最大的，方便修改就行了。

虚实剖分

这是轻重剖分的动态升级版，资瓷动态的钦点，哪些边是“实”的，哪些边是“虚”的。每个点只能有一个实儿子。然后实边连起来变成实链，将树划分成若干条链。

LCT全部都是基于虚实剖分，动态钦点重儿子，来实现链操作的。

如何维护所有的链

实链

考虑一下加边和断边的时候，如果把实链看成区间，其实就是在做区间合并和分裂操作，以及对一块区间做操作或者询问（链修改/询问）。那么什么结构可以快速的维护这东西呢？

Splay

于是维护方式为：用若干颗 \(Splay\) 维护若干个实链，每一颗 \(Splay\) 树的中序遍历，就对应一条实链从上往下的遍历。

举个栗子

这张图中，红色是实边，蓝色是虚边。

图中，\(A,B,D,H\) 在一个 Splay 里，\(E,I\) 在一个 Splay 里，\(C,G\) 在一个 Splay 里，\(F,J\) 两点都是单独一个点作为一个 Splay 的。

虚边

现在实边维护出来了，还有一个问题：虚边我也要记下来啊

既然要记下来，怎么和原来的实边区分开来？

有一个巧妙的实现，认父不认子 —— 我可能是你父亲，但你不一定是我儿子。

对于点 \(u\)，如果 \(u\) 既不是 \(fa_u\) 的左儿子，也不是右儿子，那么 \((u,fa_u)\) 这条边就是虚边了。

开始构思

我们站在 Tar 老师的角度，考虑这个算法怎么实现。

首先是功能：支持加边，删边，链修改/询问。具体怎么做呢？

你可能会想，加边不是直接合并一下两个 Splay 就完了。删边也是，直接断一下即可。

但这会破坏现在剖好的链，而且无法维护。

考虑把根换成 \(u\)，这样倒是可以直接操作。那我们就要支持一个换根操作了。

那么如何换根呢？

考虑把树想象成有向的，每条边从父亲连向儿子。那只要把 \(u\) 到根的路径边都反向一下，那 \(u\) 就是根了。由于我们用的是 Splay 维护，反向还是挺好搞的，就交换一下左右儿子即可。这个可以用 lazytag 实现。

那现在又要提取到根的路径了。这便是 LCT 的基础操作： access

具体要维护的功能（从基础到高级）

Splay部分

需要支持把每个点旋转到它 所在Splay 的根。根定义为：如果这个点和父亲连的是虚边，那它就是它所在 Splay 的根。

一开始 Splay 的根是它维护的实链最上面那个点，然而后期我们会对树做旋转，就导致 Splay 的根可能发生变化。

access(u)

这是最基本的：提取 \(u\) 到根的路径（把路径上都变成实边，并把相应的边变成虚边）。另外，它会把 \(u\) 下面的那个实边给变虚，这就使得 \(u\) 所在的 Splay 恰好变成 \(u\) 到根的路径，不多任何别的。

想起来很简单，每次把 \(u\) 给 \(Splay\) 到最顶上，然后在右儿子连接上一个跨过去的 Splay。特殊地，跨过的第一个 Splay 连空点 —— 这就把 \(u\) 下面那个实边变虚了。

为什么连右儿子？考虑现在的 Splay 维护的链是 \(a\)，上一个跨过去的链是 \(a'\)

那么我们既然要把边变成实的，就要把 \(a\) 和 \(a'\) 连起来，其中 \(a'\) 在 \(a\) 的后面，因为这次的链在上次的链上面。

所以要接在后面，体现在 Splay 的中序遍历，就是接在 右儿子

此时顺便 update 一下信息。

make(u)

把 \(u\) 变成当前树的根。

由上面所说，先 access 一下，Splay 上去。此时由 Splay 的中序遍历，我们是从最下面翻上来的，所以 \(u\) 应该在 Splay 的根，并且其他点都在它的左边（即 \(u\) 的右儿子为空）

然后打一个 lazytag 维护边的反转即可。

find(u)

老样子，先 access 一下，然后 Splay 上去

上面说了，现在所有点都在 \(u\) 左边，并且原来的那个根应该在最左边 —— 它是原树中链的顶头，在 Splay 上便是最左边的了。

然后一直走左儿子，就可以找到根了。最后找到根完了再 Splay 上去，保证复杂度

split(u,v)

打通 \(u,v\) 之间的路径，并且不剩别的

先把 \(u\) 变成根（make(u)），然后把 v 给 access 上去即可。Splay 一下保证复杂度。

link(u,v)

终于到了正题

上面说不好直接连，现在我们会换根了，make一下，然后连就可以了

注意，题目如果不保证连边合法，先 find 一下看看在不在一块

cut(u,v)

正题*2

先make(u)一下，然后来一个find(v)

find的时候要做一次access，最后把找到的根又 Splay 上去了。那么现在一定满足：

\(u\) 是根节点
\(u\) 只有一个儿子 \(v\)，并且是右儿子（由于 \(u\) 在 \(v\) 上面）。
\(u,v\) 的路径中间没有其他的点，体现在 Splay 上，就是 \(v\) 没有左儿子

然后把 \(u\) 的右儿子和 \(v\) 的父亲都设置为空，即可

复杂度

log的，不知道咋分析

网上的势能分析看不懂qaq

为何我的眼里常含泪水，因为我菜的抠脚 —— LightningUZ

talk is cheap

洛谷板子

#include <bits/stdc++.h>

using namespace std;

namespace Flandre_Scarlet

{

    #define N 1000006

    #define F(i,l,r) for(int i=l;i<=r;++i)

    #define D(i,r,l) for(int i=r;i>=l;--i)

    #define Fs(i,l,r,c) for(int i=l;i<=r;c)

    #define Ds(i,r,l,c) for(int i=r;i>=l;c)

    #define MEM(x,a) memset(x,a,sizeof(x))

    #define FK(x) MEM(x,0)

    #define Tra(i,u) for(int i=G.st(u),v=G.to(i);~i;i=G.nx(i),v=G.to(i))

    #define p_b push_back

    #define sz(a) ((int)a.size())

    #define all(a) a.begin(),a.end()

    #define iter(a,p) (a.begin()+p)

    int I() {char c=getchar(); int x=0; int f=1; while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return ((f==1)?x:-x);}

    template <typename T> void Rd(T& arg){arg=I();}

    template <typename T,typename...Types> void Rd(T& arg,Types&...args){arg=I(); Rd(args...);}

    void RA(int *p,int n) {F(i,1,n) *p=I(),++p;}

    class Link_Cut_Tree

    {

    public:

        int ch[N][2],fa[N]; // 基本, 维护splay的

        bool rv[N]; // makeroot要用的翻转标记

        int val[N],s[N]; // 其它要维护的 (这里是路径异或)

        #define ls(u) ch[u][0]

        #define rs(u) ch[u][1]

        bool id(int u) {return u==rs(fa[u]);}

        bool rt(int u) {return u!=ls(fa[u]) and u!=rs(fa[u]);}

        // 判断是否是 splay 的根

        void up(int u) // 维护信息

        {

            s[u]=s[ls(u)]^s[rs(u)]^val[u];

        }

        void revone(int u)

        {

            swap(ls(u),rs(u));

            rv[u]^=1;

        }

        void pushdown(int u) // pushdown

        {

            if (rv[u])

            {

                if (ls(u)) revone(ls(u));

                if (rs(u)) revone(rs(u));

                rv[u]=0;

            }

        }

        void pushall(int u) // 一连串的pushdown

        {

            if (!rt(u)) pushall(fa[u]);

            pushdown(u);

        }

        void rot(int u) // 最基本的旋转

        {

            int f=fa[u],f2=fa[f],i=id(u),i2=id(f),w=ch[u][i^1];

            if (!rt(f)) ch[f2][i2]=u; ch[u][i^1]=f; ch[f][i]=w;

            if (w) fa[w]=f; fa[f]=u; fa[u]=f2;

            // 这两行顺序不能反

            // 见洛谷讨论区

            up(f),up(u);

        }

        void splay(int u)

        {

            pushall(u);

            while(!rt(u)) // 这里是 while(!rt(u))，而不是 while(u)

            {

                int f=fa[u];

                if (!rt(f))

                {

                    rot(id(f)==id(u)?f:u);

                }

                rot(u);

            }

            up(u);

        }

        void access(int u) // access

        {

            for(int p=0;u;u=fa[p=u]) // p: 上一块跨过的splay的根

            {

                splay(u); rs(u)=p; up(u);

            }

        }

        void make(int u)

        {

            access(u); splay(u); revone(u);

        }

        int  find(int u)

        {

            access(u); splay(u);

            while(ls(u)) pushdown(u),u=ls(u); // 这里不要忘了先pushdown

            splay(u); return u; // 也不要忘了splay

        }

        void split(int u,int v) // 提取路径

        {

            make(u); access(v); splay(v);

        }

        void link(int u,int v)

        {

            make(u);

            if (find(v)!=u) // 判一下find

            {

                fa[u]=v;

            }

        }

        void cut(int u,int v)

        {

            make(u);

            if (find(v)==u and rs(u)==v and !ls(v)) // 判一下find*2

            {

                rs(u)=fa[v]=0;

            }

        }

    }T;

    int n,m;

    void Input()

    {

        Rd(n,m);

        F(i,1,n) T.val[i]=I();

    }

    void Sakuya()

    {

        F(i,1,m)

        {

            int o,x,y; Rd(o,x,y);

            if (o==0)

            {

                T.split(x,y);

                printf("%d\n",T.s[y]);

            }

            if (o==1)

            {

                T.link(x,y);

            }

            if (o==2)

            {

                T.cut(x,y);

            }

            if (o==3)

            {

                T.splay(x);

                T.val[x]=y;

            }

        }

    }

    void IsMyWife()

    {

        Input();

        Sakuya();

    }

}

#undef int //long long

int main()

{

    Flandre_Scarlet::IsMyWife();

    getchar();

    return 0;

}

巴特西