LCT小记

command_block · 2020-04-11 18:03:03 · 算法·理论

LCT本体

LCT是维护动态森林的数据结构。

支持 : 连边，断边，换根，提取路径等等操作。是一个强大的数据结构。

首先我们先来看基本原理 : 实链剖分。

或许你听说过重链剖分，那是维护静态树路径的利器，但是这里是动态的，所以固定的剖分方式容易出锅。

实链剖分就是一种动态的剖分方式，随着操作自适应地剖。具体咋剖可看下文。

注意 : LCT 的具体实现是经过精细设计的。所以要先接受一些钦定和假设,最终才能顺利地讲述算法流程。

我们把剖出来的链条用平衡树维护，链上的点以深度为序。

这里绝大多数时候要使用Splay，因为精细设计，只有与Splay才能配合默契。请先熟悉Splay的基本操作。

我们如何将若干条链组合成一棵树呢? 我们令链的Splay根节点指向整条链在原树中的父亲，而这个父亲并不记录这个儿子，即“认父不认子”。

下面给出一些Splay相关操作，注意一些特殊的细节。

可以看到维护了翻转标记，有什么用后面再说。

struct Node{
  int l,r,f,s,x;bool fl;
  inline void ladd()
  {fl^=1;swap(l,r);}
}a[MaxN];
inline bool nrt(int u)
{return a[a[u].f].l==u||a[a[u].f].r==u;}
inline void up(int u)
{a[u].s=a[a[u].l].s^a[a[u].r].s^a[u].x;}
inline void ladd(int u){
  if (a[u].fl){
    a[a[u].l].ladd();
    a[a[u].r].ladd();
    a[u].fl=0;
  }
}
inline void rot(int u)
{
  int fa=a[u].f,gf=a[fa].f;
  ladd(fa);ladd(u);
  a[a[fa].f=u].f=gf;
  if (a[gf].l==fa)a[gf].l=u;
  if (a[gf].r==fa)a[gf].r=u;
  //记住要写成两个if,不然会出现0有儿子的情况
  if (a[fa].l==u){
    a[a[fa].l=a[u].r].f=fa;
    a[u].r=fa;
  }else {
    a[a[fa].r=a[u].l].f=fa;
    a[u].l=fa;
  }up(fa);up(u);
}
int st[MaxN],tn;
void splay(int u)
{
  int v=u;tn=0;
  for (;nrt(v);v=a[v].f)st[++tn]=v;
  st[++tn]=v;
  for (int i=tn;i;i--)ladd(st[i]);
  //先将路径上的所有标记推走
  while(nrt(u)){
    int fa=a[u].f,gf=a[fa].f;
    if (nrt(fa)&&((a[gf].l==fa)==(a[fa].l==u)))
      rot(fa);
    rot(u);
  }
}

• Access 操作

  作用 : 将根到 u 的路径提取到一个Splay中。

这个操作是 LCT 的精华部分和关键。

现在的情况如下图 :

第一步，我们要先切断 u,v 之间的重边，把链分成两段。如下图:

具体操作就是把 u 旋到根，然后让比 u 更深的右侧子树“另立门户”。

然后，来到 u 这条链的父亲 v ，我们要把这条链打通。如下图:

首先，要把 v 更深的链除去，方法同上。

然后 v 在 Splay 的根部，右儿子是空的，正好放下 u ，则合为一条链。

然后发现已经到达整棵树的根 R ，停止操作。

代码出奇的简洁:

void access(int u)
{
  for (int v=0;u;v=u,u=a[u].f){
    splay(u);
    a[u].r=v;up(u);
  }
}

解释一下。首先 splay(x) ，把当前重链划分成两半。

然后把 x 的右儿子(更深处)替换成上一层的重链顶，此时原来的岔路成为了“干儿子”。

然后对 x 的信息进行更新，将 y 记录为 x (上一层重链顶)，跳跃至下一条重链。

这也回答了上面“怎么剖”的问题。

事实上，这样看似乱剖，其实每次剖时相当于在到根的链上做splay。

累加势能即可得到和单棵Splay类似的结果 : 均摊 O(\log n)。

这个模型也同样可以迁移到其他的题目，比如 P6292 【模板】区间本质不同子串个数

• Makeroot 操作

  作用 : 将 u 置为当前树的根。

我们来思考祖先关系是由什么表示的，答案是“认父不认子”和“按深度排序”两个体系。

我们先执行 access(u) ，然后 u 和当前根就只按“按深度排序”规则来管理祖先关系了。

现在，把整棵树翻转，相当于把这一条链的父边方向反转了， u 就变为了根。

代码同样十分简洁:

void makrt(int u)
{access(u);splay(u);a[u].ladd();}

• Spilt操作

  作用 : 将 u,v 之间的路径整理到同一个 Splay 中，并以 v 为平衡树根。

首先令 u 为整棵树的根，打通 y 与根之间的路径,最后 splay(v) 即可。

void spilt(int u,int v)
{makrt(u);access(v);splay(v);}

• Findroot操作

  作用 : 查询 u 所在的树的树根。

前面讲到过，祖先关系的表示比较复杂，所以找根也略微有点复杂。

同样先执行 access(u) ，然后在当前 Splay 中找到最浅点即可，别忘记推懒标记。

找到了之后需要 splay(u) 一下，否则复杂度可能退化。

int findrt(int u)
{
  access(u);splay(u);
  while(a[u].l){ladd(u);u=a[u].l;}
  splay(u);return u;
}

• Link操作

  作用 : 在当前森林中连边 u\leftrightarrow v。

先执行 makert(u) ，让 u 能够代表整个联通块，然后令 u 认 v 为“干爹”即可。

注意，如果此时 findrt(v)=u ，则表示 u,v 本就在同一连通块内，无需操作。

void link(int u,int v)
{
  makrt(u);
  if (findrt(v)==u)return ;
  a[u].f=v;
}

• Cut操作

  作用 : 在当前森林中删去边 u\leftrightarrow v。

首先执行 spilt(u,v) ，如果 u,v 在原树中直接连接，此时 v 的左子树中一定有且只有 u ，否则这条边不存在。

否则让 u,v 之间断绝一切父子关系即可。记得更新 v 的信息。

void cut(int u,int v)
{
  spilt(u,v);
  if (a[v].l!=u||a[u].l!=a[u].r)return ;
  a[v].l=a[u].f=0;up(v);
}

复杂度为 O\big((n+m)\log n\big)。

#include<algorithm>
#include<cstdio>
#define MaxN 105000
using namespace std;
int read(){
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
struct Node{
  int l,r,f,s,x;bool fl;
  inline void ladd()
  {fl^=1;swap(l,r);}
}a[MaxN];
inline bool nrt(int u)
{return a[a[u].f].l==u||a[a[u].f].r==u;}
inline void up(int u)
{a[u].s=a[a[u].l].s^a[a[u].r].s^a[u].x;}
inline void ladd(int u){
  if (a[u].fl){
    a[a[u].l].ladd();
    a[a[u].r].ladd();
    a[u].fl=0;
  }
}
inline void rot(int u)
{
  int fa=a[u].f,gf=a[fa].f;
  a[a[fa].f=u].f=gf;
  if (a[gf].l==fa)a[gf].l=u;
  if (a[gf].r==fa)a[gf].r=u;
  if (a[fa].l==u){
    a[a[fa].l=a[u].r].f=fa;
    a[u].r=fa;
  }else {
    a[a[fa].r=a[u].l].f=fa;
    a[u].l=fa;
  }up(fa);up(u);
}
int st[MaxN],tn;
void splay(int u)
{
  int v=u;tn=0;
  for (;nrt(v);v=a[v].f)st[++tn]=v;
  st[++tn]=v;
  for (int i=tn;i;i--)ladd(st[i]);
  while(nrt(u)){
    int fa=a[u].f,gf=a[fa].f;
    if (nrt(fa)&&((a[gf].l==fa)==(a[fa].l==u)))
      rot(fa);
    rot(u);
  }
}
void access(int u)
{
  for (int v=0;u;v=u,u=a[u].f){
    splay(u);
    a[u].r=v;up(u);
  }
}
void makrt(int u)
{access(u);splay(u);a[u].ladd();}
int findrt(int u)
{
  access(u);splay(u);
  while(a[u].l){ladd(u);u=a[u].l;}
  splay(u);return u;
}
void spilt(int u,int v)
{makrt(u);access(v);splay(v);}
void link(int u,int v)
{
  makrt(u);
  if (findrt(v)==u)return ;
  a[u].f=v;
}
void cut(int u,int v)
{
  spilt(u,v);
  if (a[v].l!=u||a[u].l!=a[u].r)return ;
  a[v].l=a[u].f=0;up(v);
}
int n,m;
int main()
{
  n=read();m=read();
  for (int i=1;i<=n;i++)a[i].x=read();
  for (int i=1,ord,u,v;i<=m;i++){
    ord=read();u=read();v=read();
    if (ord==0){spilt(u,v);printf("%d\n",a[v].s);}
    if (ord==1)link(u,v);
    if (ord==2)cut(u,v);
    if (ord==3){splay(u);a[u].x=v;up(u);}
  }return 0;
}

• 易错点

  • rot(u) 中连父边的双 if。

  • splay(u) 中双旋一定要确定不是根，因为 rot(u) 不能对根使用。

  • access 中的 y 初值一定要赋为 0 。

  • 该 access 要 access (统一平衡树),该 splay 要 splay (代表整棵树)

  • findrt 里面的推标记。

  • link/cut 里面无用操作的判据(头脑清醒应该不会错)

• 调试方法

  LCT 的有效部分长度仅为 1.3Kb ，我花了 10min 就写完了。

  但是代码虽简洁，却很难调，后面的时间都用在调试上了。

  • 静态查错 : 比较推荐的方法，毕竟代码短，看的东西不多，对照常犯的错误检查即可。

  • 动态查错 :

  这些函数是层层嵌套的，所以要先快速找到断点，麻烦的是断点之间还有因果关系，要不断回溯。

  一般来讲，如果写挂了，小数据就会锅，一个比较方便的方法是输出全部点的连接信息。

  而且，切莫以为某个函数写对了，就不需要调试信息。往往底层函数的调试信息更能揭示因果关系。

  • 机器查错 : 有些时候样例太水，过了仍然很慌咋办……

  某些题目需要转化后使用 LCT ，这时建议先单独对 LCT 调试而不是大杂烩。

  LCT 挂的形式一般表现为死循环或者 RE ，这就不需要对拍了。

  如果还是想拍，写个邻接矩阵 DFS 似乎不错，反正数据不需要太大。

说句闲话，我的代码毫无复杂的卡常，比大多数正常写法的人都短，似乎在模板里面跑得挺快?

现在洛谷评测机有和当年性能差，旧的提交记录更快，排到了最优解第一页……(瞻仰论文哥)

此外， LCT 在某种程度上比树剖好写 (对于静态树无需 link/cut 更好写) ，所以可以在部分题目中代替树剖，特别是细节多的题目。

• 例题① P1501 [国家集训队]Tree II

LCT \times P3373 【模板】线段树 2

简单推标记练习，熟悉板子。

• 例题② P2173 [ZJOI2012]网络

同样近乎于模板题，对每种颜色开一个LCT维护即可。

• 进阶题 P3703 [SDOI2017]树点涂色

好的性质题，每次从 u 到根染上新颜色这个设定一看就很像 access。

观察到每个点到根的轻边个数，发现正好等于颜色个数，因为颜色是不会交替出现的。

每次切换轻重边，就对受到影响的子树在 dfs 线段树上操作。

对于操作 2 ，由于 V 字形路径的两个岔路必然不包含相同的颜色，可以直接累加。

答案即为 dep[u]+dep[v]-2*dep[lca(u,v)]+1 ，最后要 +1 是因为算上 lca 本身的颜色。

对于操作 3 ，取一个子树最大值即可。

LCT维护子树

前文只提到了 LCT 维护路径，然而在维护子树上似乎比较无力。

事实上，借助一些技巧，我们还是能维护一些子树信息的。(但是不能修改)

注意到，我们丢失了子树信息，根本原因是我们使虚边“认父不认子”。

我们考虑维护一个“虚子树和”，即所有虚边儿子的权值和，这只需要在 access/link 里面修改，在 Splay 上可以视作这个点的“附加权值”来维护。

进行 access 时，我们会有更换右儿子的操作，这时我们要把 u 原来的右儿子的 LCT 子树信息加入 u 的虚子树信息，把 u 的新的右儿子的 LCT 子树信息从 u 的虚子树信息中除去。这要求贡献可逆。

进行 link 时，我们会先把点 u 置为根,然后连一条 u 到 v 的虚边，这时我们发现不仅 v 的虚子树信息需要加入 u 的 LCT 子树信息， v 的所有祖先的 LCT 子树信息也需要更改。

我们先提前对 v access 再 splay 就行了，这样子单独修改 v 即可。

进行 cut 时，我们会先提出 (u,v) 的路径，此时断开的是实边所以无需改动。

注意，由于 Splay 的求和，我们并不能任意取用子树和，而必须要 splay(u) 之后去掉左子树更浅的贡献。

• 例题 P4219 [BJOI2014]大融合

查询边的负载，实际上就是边两侧点数的乘积。

对于边 (u,v) ，我们先 makert(u) 。