LCT 全机房都学的 flashhu 大佬的博客 https://www.cnblogs.com/flashhu/p/8324551.html , 两个月前学的, 但有些地方没有理解, 导致出锅, 这里来总结一下8,(然而并不打算详细讲解基础内容, 主要是总结)
基本性质
LCT 利用 splay 可以改变树的结构实现动态, 通过实链剖分维护信息, 所以分为两种边 --- 实边和虚边, 每个由实边组成的连通块是一个 splay, 虚边维护 splay 间的父子关系 (连通块的关系). 链剖链剖, 要求从上剖到下, 就像择菜一样, 所以不会存在一个 splay 中深度相同的情况. 其次, splay 中按深度为关键字, 所以随左节点的就是整个 splay 最高的节点, 虚边连向它在原树的父亲
认父不认子:
"子" 指 son 数组 (我习惯这么叫), 它是 splay 中的结构关系, 有的孩子就没有连边, 而孩子总是想念着爹爹, 以连通块的方式整体连过去
关于 update 的问题, 这个问题困扰多时, 有的大佬说, 这么多 update 太麻烦, 他的 access, cut, link 等等函数均没有 update, 但没出过问题, 原因在于 splay 的时候会一口气 update, 而操作完以后大部分情况都要 splay, 但据他说后来出了一些锅, access 加了 update 就过了, 所以建议大家保险一点, 常数大把时间复杂度松一下就行了
关于 pushr 函数, 我反正是没有的, 多年习惯, 好像还没出事, 不过遇到特殊题型确实要注意, 比如在 findroot 的时候要 spread, 有时候也会比较麻烦, 不过习惯了熟练了锅也就少了
关于 cut 函数: 让 x 成为根, f[x] 肯定是 0 了, 这时候连一下 y 岂不美哉
关于 link 函数: 打通 x, y 之路, 旋 y 为根, 断 x, y 岂不易乎
代码贴上:
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- using namespace std;
- const int N = 400050;
- const int INF = 0x7fffffff;
- int read(void) {
- int x = 0; bool f = 0;
- char c = getchar();
- for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
- for (;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
- return f ? -x : x;
- }
- int s[N], son[N][2];
- int tag[N], f[N], n, sz;
- int st[N], v[N];
- inline bool nroot(int x) {
- return son[f[x]][0] == x || son[f[x]][1] == x;
- }
- inline void update(int x) {
- s[x] = s[son[x][0]] ^ s[son[x][1]] ^ v[x];
- }
- inline void spread(int x) {
- if (!tag[x]) return;
- swap(son[x][1], son[x][0]);
- tag[son[x][0]] ^= 1;
- tag[son[x][1]] ^= 1;
- tag[x] = 0;
- }
- inline void rotate(int x) {
- int y = f[x], z = f[y];
- int k = son[y][1] == x, w = son[x][k^1];
- if (nroot(y)) son[z][son[z][1]==y] = x;
- son[x][k^1] = y, son[y][k] = w;
- if (w) f[w] = y; f[y] = x, f[x] = z;
- update(y);
- }
- inline void splay(int x) {
- int y = x, z = 0; st[++z] = y;
- while (nroot(y)) st[++z] = y = f[y];
- while (z) spread(st[z--]);
- while (nroot(x)) {
- y = f[x], z = f[y];
- if (nroot(y)) {
- if ((son[y][0]==x)^(son[z][0]==y))
- rotate(x);
- else rotate(y);
- }
- rotate(x);
- }
- update(x);
- }
- inline void access(int x) {
- for (int y = 0; x; x = f[y = x])
- splay(x), son[x][1] = y, update(x);
- }
- inline void makeroot(int x) {
- access(x); splay(x);
- tag[x] ^= 1;
- }
- int findroot(int x) {
- access(x); splay(x); spread(x);
- while (son[x][0]) x = son[x][0], spread(x);
- splay(x);
- return x;
- }
- inline void split(int x,int y) {
- makeroot(x);
- access(y); splay(y);
- }
- 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 && !son[y][0])
- f[y] = son[x][1] = 0;
- }
- int main() {
- int n = read(), m = read();
- for (int i = 1;i <= n; i++) v[i] = read();
- while (m--) {
- int type = read(), x = read(), y = read();
- switch(type) {
- case 0 : split(x, y); printf ("%d\n", s[y]); break;
- case 1 : link(x, y); break;
- case 2 : cut(x, y); break;
- case 3 : splay(x); v[x] = y;
- }
- }
- return 0;
- }
进阶与应用!!!:
flashhu 巨佬的 blog https://www.cnblogs.com/flashhu/p/9498517.html
平衡树操作:
没啥意思, 就是把平衡树的题目强行出到树上, 在动态一下
如果深入掌握平衡树因该不是很难
连通性:
把 LCT 当可断并查集用, 应用比较广泛, 也不是很难
上面的可以当板子敲一敲熟练度
维护树上信息:
这类题和 LCT 关系要大一些了, 主要是利用 LCT 的核心操作 ---Access
在断开一条实边, 连一条虚边的时候将虚实之间的关系实现转化和统计, 是非常巧妙的做法
做一做例题相信会大有感觉
维护染色连通块:
常用套路是维护多棵 LCT, 每棵维护不同的颜色, 在单棵树上的连通块颜色相同, 可以借此维护信息, 有时候要把消点操作通过唯一性映射到与父亲的连边转化为消边操作, 这个也是很巧妙的
像树点涂色这样的题, 维护了 access 到根节点要跳几次轻链, 可以说是 LCT 的高级应用, 必须要有对 LCT 的深入理解才可
特殊题型:
暂时没做, 咕咕咕
总结:
总的来说 LCT 有很简单的板子题, 也有需要人类智慧的神仙题, 需要多刷一些题, 方能掌握更多的方法
来源: http://www.bubuko.com/infodetail-3400380.html