LCT 小记

2023-11-18 12:40:16

这次不是整活了，记个笔记，加深下印象。

\(\text{1. LCT}\) 引入

题目描述

给定 \(n\) 个点以及每个点的权值，要你处理接下来的 \(m\) 个操作。
操作有四种，操作从 \(0\) 到 \(3\) 编号。点从 \(1\) 到 \(n\) 编号。

  • 0 x y 代表询问从 \(x\) 到 \(y\) 的路径上的点的权值的 \(\text{xor}\) 和。保证 \(x\) 到 \(y\) 是联通的。
  • 1 x y 代表连接 \(x\) 到 \(y\)，若 \(x\) 到 \(y\) 已经联通则无需连接。
  • 2 x y 代表删除边 \((x,y)\)，不保证边 \((x,y)\) 存在。
  • 3 x y 代表将点 \(x\) 上的权值变成 \(y\)。

动态树问题，我们可以用 \(\text{LCT}\) 进行解决，这是一类问题，而不是某个单独的数据结构。

\(\text{2. LCT}\) 相关定义

实链剖分

我们回顾以往遇到树链问题的常用解决方法：树链剖分。

树链剖分实质上依赖于重链剖分，而 \(\text{LCT}\) 依赖于实链剖分。

实链剖分划分出的边叫实边和虚边。

对于每个节点它最多只能向一个儿子延申一条实边，不是实边的边被定义为虚边。

实边的划分相对*，可以任意选择一个儿子作为实边。

由上面几句话可自行归纳出一些关于实链剖分的事：

\(1.\) 实链与另一条实链之间由虚边连接

\(2.\) 节点 \(x\) 最多只会向众多儿子连一条实边，其他儿子和 \(x\) 间均为虚边

\(3.\) 节点 \(x\) 最多只会连一条实边，也可以不连实边

类比树剖和实边定义就可。

例如下图中，有两条实链 \(\{ 1 \rightarrow 3 \rightarrow 6\}\) 和 \(\{ 2 \rightarrow 4 \rightarrow 8 \}\) 。

实边的选择是很*的，也可令 \(1 \rightarrow 3\) 的这条边不为实边，反而令 \(1 \rightarrow 2\) 为实边，则其他边不动的情况下，实链变为了 \(\{1 \rightarrow 2 \rightarrow 4 \rightarrow 8 \}\) 和 \(\{ 3 \rightarrow 6\}\)

LCT 小记

维护方式

因为虚实边的划分是动态的，所以采用了灵活的 \(\text{spaly}\) 维护，而不能使用静态的数据结构类似线段树之类的。

可以用 \(\text{fhq treap}\) 写，不过貌似会多个 \(\log\) 。

\(\text{LCT}\) 中的 \(\text{splay}\) 维护的是实链，要求 \(\text{splay}\) 的中序遍历为自顶向下的实链。

注意这里一个单独的点也被 \(\text{splay}\) 维护着，因为伴随着实边虚边的划分，这个点可能成为实链中的一部分。

另外地，一个点只可能存在于一个 \(\text{splay}\) 中。

下图展示了图中树 \(\text{splay}\) 所维护的链：

LCT 小记

因为一条实链被一个 \(\text{splay}\) 所维护着，又因为一条实链与一条实链之间由虚边连接。

所以变相的说，一个 \(\text{splay}\) 和另一个 \(\text{splay}\) 之间由虚边连接。

然后 \(\text{splay}\) 由深度更大的指向深度小的，而不将深度小的指向深度大的，理由很显然。

\(\text{3. LCT}\) 操作

首先需要申明自己的结构体，不然别人看不懂。

struct node {
  int ch[2], fa, val, sum, tag;
  //ch[0/1] 表示左儿子还是右儿子
  //fa 表示父亲
  //val 表示当前节点权值
  //sum 表示子树权值
  //tag 表示翻转等操作要用的懒标记
} s[N];

\(\text{splay}\) 中的改动函数

上文中我们发现在 \(\text{LCT}\) 中 \(\text{splay}\) 的父亲关系与普通的 \(\text{splay}\) 有所不同。

对于父亲的判断上，我们不仅需要判断他是他父亲的左儿子还是右儿子，还需要判断他是否为一条实链的根节点。

判断的方式利用之前提到的，深度小的 \(\text{splay}\) 不会指向深度大的 \(\text{splay}\) ，判断他的父亲的左右儿子中是否有他，如果没有则为一条实链顶端。

int chk(int k) {
  if(s[ s[k].fa ].ch[0] == k) return 0; // 表示是左儿子
  if(s[ s[k].fa ].ch[1] == k) return 1; // 表示是右儿子
  return -1; //表示是链顶端
}

同理的 \(\text{rotate}\) 和 \(\text{splay}\) 函数也有一点小的改动：

void connect(int k,int fa,int op) {
  s[k].fa = fa;
  if(op == 1) s[fa].ch[1] = k;
  if(op == 0) s[fa].ch[0] = k;
}
void rotate(int x) {
  int y = s[x].fa, z = s[y].fa;
  int sx = chk(x), sy = chk(y), u = 0;
  if(sx == 1) u = s[x].ch[0];//改动在这里
  if(sx == 0) u = s[x].ch[1];//改动在这里
  connect(u, y, sx);  connect(y, x, sx ^ 1);  connect(x, z, sy);
  //改动在这里
  pushup(y);  pushup(x);
}
void splay(int k) {
  while( chk(k) != - 1 ) { //改为判断是否转到了链顶端
    int y = s[k].fa;
    if(chk(y) == -1) rotate(k); //只能转一次
    else if(chk(y) == chk(k)) rotate(y), rotate(k);
    else rotate(k), rotate(k);
  }
}

\(\text{LCT}\) 中的 \(\text{access}\) 操作

这个操作是 \(\text{LCT}\) 强大功能的基础，\(\text{access(x)}\) 表示将整棵树的根到 \(x\) 的路径变为实链。

如下图，我们要执行 \(\text{access(6)}\) 。

LCT 小记

则执行完后的图长这样：

LCT 小记

对于这条路径的处理，首先我们要将路径末的节点上连接的实边全部换为虚边，因为 \(\text{access}\) 求出的 \(1 \rightarrow 6\) 的路径，如果下面还有实边，则会变为 \(1 \rightarrow 7\) 的路径。

同时对于路径上的虚边，要将它变为实边，再将他所连接的父亲本来所连接的实边换为虚边。

假设我们在执行 \(\text{access(x)}\) 操作。

这个的执行过程很简单，考虑对 \(x\) 到根节点的链从下往上考虑。

对于每个点，先将他转到他所在的 \(\text{splay}\) 的根节点。

然后每次改变他的右儿子的值为他下面的那个节点，如果是最底层节点则设为 \(0\) 。

因为是他的下层节点，我们都知道的，每个 \(\text{splay}\) 的中序遍历是自顶向下的实链，那么在下层的节点在 \(\text{splay}\) 中就处于右边。

对于这个操作重复执行就可了。

复杂度是 \(\log n\) 的， \(\text{splay}\) 可以让树高均摊下来为 \(\log n\) ，这也是使用 \(\text{splay}\) 的一个主要原因。

代码很短：

void access(int k) {
  int son = 0;
  while(k) {
   splay(k);
   s[k].ch[1] = son;  pushup(k);
   son = k; k = s[k].fa;
  }
}

\(\text{LCT}\) 中的 \(\text{findrt}\) 操作

查找 \(x\) 所在的连通块的根，先 \(\text{access(x)}\) ，根节点一定是当前 \(\text{splay}\) 中最小的结点，一直向左即可，最后 \(\text{splay}\) 一下根节点。

int findrt(int k) {
  access(k);  splay(k);
  while(s[k].ch[0]) pushdown(k), k = s[k].ch[0];
  splay(k);  return k;
}

这个操作后找到的根，成为了他所在连通块的根。

\(\text{LCT}\) 中的 \(\text{makeroot}\) 操作

将 \(x\) 点设为所在连通块的根。

首先打通 \(x\) 与根节点的路径，此时 \(x\) 为 \(\text{splay}\) 中深度最大的，在最右边，然后根节点为深度最小的，在最左边。

本质就是一个区间翻转了，于是 \(\text{splay}\) 加个 \(\text{tag}\) 维护一下就好了。

void pushdown(int k) {
  if(s[k].tag) {
    swap(s[k].ch[0], s[k].ch[1]);
    if(s[k].ch[0]) s[s[k].ch[0]].tag ^= 1;
    if(s[k].ch[1]) s[s[k].ch[1]].tag ^= 1;
    s[k].tag = 0;
  }
}
void pushall(int k) {
  if(chk(k) != -1) pushall(s[k].fa);
  pushdown(k);
}

然后这样在 \(\text{splay}\) 操作开头需要添加一行 \(\text{pushall(k)}\) 。

\(\text{LCT}\) 中的 \(\text{spilt(x, y)}\) 操作

将 \(x\) 和 \(y\) 之间的路径拉成一条实链。

那简单，将 \(x\) 设为所在连通块根之后，与 \(y\) 拉出一条路径就好了。

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

在经过这个操作之后, \(y\) 成为了 \(x\) 的父亲，\(x\) 为 \(y\) 的左儿子。

\(\text{LCT}\) 中的 \(\text{link(x, y)}\) 操作

这就是加边操作了，感觉好简单。

先将 \(x\) 变成所在连通块根，然后直接看 \(y\) 在不在这个连通块，没有直接将 \(x\) 父亲设为 \(y\) 就好了。

void link(int x,int y) {
  makeroot(x);
  if(findrt(y) == x) return;
  s[x].fa = y;
}

\(\text{LCT}\) 中的 \(\text{cut(x, y)}\) 操作

删边操作，写锅了好几次，最后还是看了别人的/ll

首先将 \(x\) 设为根，然后判断 \(x, y\) 在不在同一个连通块，不在证明不存在这个边。

然后，由于判断在同一连通块的时候，采用的是 findrt(y) == x 这个时候执行了 \(\text{findrt(y)}\) 于是，此时 \(x\) 仍然为连通块根节点，然后 \(x\) 为他的左儿子。

然后当 \(y\) 为 \(\text{splay}\) 中 \(x\) 的下一位才会有边，于是判断一下，杀完了。

bool cut(int x,int y) {
  makeroot(x);
  if(findrt(y) != x || s[y].ch[0] || s[y].fa != x) return 0;
  s[y].fa = s[x].ch[1] = 0;
  pushup(x);
  return 1;
}

放上洛谷模板题目代码：

// 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱
// 德丽莎的可爱在于德丽莎很可爱，德丽莎为什么很可爱呢，这是因为德丽莎很可爱！
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6;
int n, m, a[N];
struct node {
  int ch[2], fa, val, sum, tag;
} s[N];
void pushup(int k) {
  s[k].sum = s[ s[k].ch[0] ].sum ^ s[ s[k].ch[1] ].sum ^ s[k].val;
}
void pushdown(int k) {
  if(s[k].tag) {
    swap(s[k].ch[0], s[k].ch[1]);
    if(s[k].ch[0]) s[s[k].ch[0]].tag ^= 1;
    if(s[k].ch[1]) s[s[k].ch[1]].tag ^= 1;
    s[k].tag = 0;
  }
}
int chk(int k) {
  if(s[ s[k].fa ].ch[1] == k) return 1;
  if(s[ s[k].fa ].ch[0] == k) return 0;
  return -1;
}
void pushall(int k) {
  if(chk(k) != -1) pushall(s[k].fa);
  pushdown(k);
}
void connect(int k,int fa,int op) {
  s[k].fa = fa;
  if(op == 1) s[fa].ch[1] = k;
  if(op == 0) s[fa].ch[0] = k;
}
void rotate(int x) {
  int y = s[x].fa, z = s[y]. fa;
  int sx = chk(x), sy = chk(y), u = 0;
  if(sx == 1) u = s[x].ch[0];
  if(sx == 0) u = s[x].ch[1];
  connect(u, y, sx);  connect(y, x, sx ^ 1);  connect(x, z, sy);
  pushup(y);  pushup(x);
}
void splay(int k) {
  pushall(k);
  while(chk(k) != -1) {
    int y = s[k].fa;
    if(chk(y) == -1) rotate(k);
    else if(chk(k) == chk(y)) rotate(y), rotate(k);
    else rotate(k), rotate(k);
  }
}
void access(int k) {
  int son = 0;
  while(k) {
    splay(k);
    s[k].ch[1] = son;  pushup(k);
    son = k; k = s[k].fa;
  }
}
void makeroot(int k) {
  access(k);  splay(k);
  swap(s[k].ch[0], s[k].ch[1]);
  if(s[k].ch[0]) s[s[k].ch[0]].tag ^= 1;
  if(s[k].ch[1]) s[s[k].ch[1]].tag ^= 1;
}
void spilt(int x,int y) {
  makeroot(x);  access(y);  splay(y);
}
int findrt(int k) {
  access(k);  splay(k);
  while(s[k].ch[0]) pushdown(k), k = s[k].ch[0];
  splay(k);  return k;
}
void link(int x,int y) {
  makeroot(x);
  if(findrt(y) == x) return;
  s[x].fa = y;
}
bool cut(int x,int y) {
  makeroot(x);
  if(findrt(y) != x || s[y].ch[0] || s[y].fa != x) return 0;
  s[y].fa = s[x].ch[1] = 0;
  pushup(x);
  return 1;
}
signed main () {
  ios :: sync_with_stdio( 0 );
  cin.tie( 0 ), cout.tie( 0 );
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> s[i].val, s[i].sum = s[i].val;
  for(int i = 1; i <= m; i++) {
    int op, x, y;  cin >> op >> x >> y;
    if(op == 0) spilt(x, y), cout << s[y].sum << "\n";
    if(op == 1) link(x, y);
    if(op == 2) cut(x, y);
    if(op == 3) splay(x), s[x].val = y;
  }
  return 0;
}

未完待续， lct 很好玩的/mgx

上一篇：寒假C练习_3


下一篇：有效的括号