LCT 学习笔记中哪些应用最广泛？

动态树 目录动态树前置：splayrotate(x)splay(x)LCT思想：实链剖分实现splay 部分fa[x]push_up(i)push_down(i)isrt(x)lazytag(i)get(x)rotate(x)splay(x)access(x)find(x)makeroot(x)link(u, v)cnt(u, v)完整代码 注意作者有以下习惯： #define el cout << '\n' #define AC return #define AK return 0 #define ls(i) ch[i][0] #define rs(i) ch[i][1] #define void inline void #define il inline 前置：splay 普通的二叉搜索树，为了使其保持深度为 \(\log n\)，每次将插入的点旋转到根。 代码在 lct 讲解部分会贴有。这里不讲解单独作为平衡树的写法，毕竟其不如 fhqtreap 一根。 rotate(x) 单次旋转，保证树的中序遍历不变。画个图可以理解。 splay(x) 将点旋转到根。 对于一个点，如果其父亲和自己都是其父亲的左或右儿子（即左右相同），转父亲均摊更优，否则转自己均摊更优。 单次最劣 \(O(n)\)，均摊 \(O( \log n)\)。 LCT 利用 splay 实现的文艺平衡树，维护动态树上区间问题，支持加边减边。 思想：实链剖分 树链剖分的一种。随意钦定点作为重儿子，方便维护动态的值。 实现 splay 部分 splay 充当文艺平衡树维护一个实链，左边为父亲，右边为儿子。 fa[x] 当 \(x\) 为所在 splay 的根，\(fa_x\) 为其在树上的父亲； 否则，\(fa_x\) 表示其在 splay 上的父亲。 push_up(i) 这个不用过多解释吧，根据题目要维护的信息写。 void push_up(int i) { siz[i] = siz[ls(i)] + siz[rs(i)] + 1; } push_down(i) lct 上的 splay 需要支持区间反转。 void push_down(int i) { if(!tag[i]) AC; tag[ls(i)] ^= 1, tag[rs(i)] ^= 1; swap(ls(ls(i)), rs(ls(i))); swap(ls(rs(i)), rs(rs(i))); tag[i] = 0; } isrt(x) 返回 \(x\) 是否为所在 splay 的根。 #define isrt(x) (ls(fa[x]) ^ x && rs(fa[x]) ^ x) lazytag(i) 暴力跳根并 pushdown 方便 splay 操作。 void lazytag(int i) { if(!isrt(i)) lazytag(fa[i]); push_down(i); } get(x) 若为 \(0\) 则为父亲的左儿子，\(1\) 为右儿子 #define get(x) (x == rs(fa[x])) rotate(x) void rotate(int x) { int y = fa[x], z = fa[fa[x]], tx = get(x), ty = get(fa[x]); if(!isrt(y)) ch[z][ty] = x; ch[y][tx] = ch[x][tx ^ 1], fa[ch[x][tx ^ 1]] = y; ch[x][tx ^ 1] = y, fa[y] = x, fa[x] = z; // 画图后很好理解 push_up(y); push_up(x); } splay(x) void splay(int x) { lazytag(x); while(!isrt(x)) { int y = fa[x], z = fa[fa[x]]; if(!isrt(y)) { if((ls(z) == y) == (ls(y) == x)) rotate(y); // 全左和全右转父亲复杂度更优 else rotate(x); // 非全左或全右转自己更优 } rotate(x); // 转两次 } } 终于讲完 splay 了，果然是依托。 access(x) 将 \(x\) 到树根变成实链。整个 lct 最核心的功能，就像 split() 和 merge() 对于 fhqtreap 一样。有了 access() 就可以干很多事情了。 方法很暴力，将 \(x\) 到根上的所有点的所有 splay 暴力加进一个 splay 即可。 int access(int x) { for(int lst = 0; x; lst = x, x = fa[x]) { splay(x); rs(x) = lst; push_up(x); if(!fa[x]) break; } return x; // splay 的根 } find(x) 找原树的父亲，注意会受后面 makeroot() 的影响。 int find(int x) { access(x); splay(x); while(ls(x)) x = ls(x); splay(x); // 转回去可以减小常数 return x; } makeroot(x) 后面的函数就既好写又好理解了。 void makeroot(int x) { access(x); splay(x); tag[x] ^= 1; swap(ls(x), rs(x)); } link(u, v) 添加 \(u\) 与 \(v\) 的边。 考虑将其中一个点所在树变为另一个的子树，这里我们选择 \(u\)。于是我们可以选择将 \(u\) 变成其子树的根并将 \(fa_u\) 改成 \(v\) 即可。 void link(int u, int v) { if(find(u) == find(v)) AC; makeroot(u); fa[u] = v; } cnt(u, v) 断掉 \(u\) 与 \(v\) 的边。 还是把其中一个转成根，另一个设成实链，splay 树上两点一定就是父亲与儿子的关系，直接修改即可。 void cut(int u, int v) { if(find(u) != find(v)) AC; makeroot(u); access(v); splay(v); if(ls(v) == u) { ls(v) = 0; fa[u] = 0; push_up(v); } } 完整代码 class LCT { private: int ch[maxn][2], tag[maxn], siz[maxn], fa[maxn]; void push_up(int i) { siz[i] = siz[ls(i)] + siz[rs(i)] + 1; } void push_down(int i) { if(!tag[i]) AC; tag[ls(i)] ^= 1, tag[rs(i)] ^= 1; swap(ls(ls(i)), rs(ls(i))); swap(ls(rs(i)), rs(rs(i))); tag[i] = 0; } #define isrt(x) (x ^ ls(fa[x]) && x ^ rs(fa[x])) void lazytag(int i) { if(!isrt(i)) lazytag(fa[i]); push_down(i); } #define get(x) (x == rs(fa[x])) void rotate(int x) { int y = fa[x], z = fa[fa[x]], tx = get(x), ty = get(fa[x]); if(!isrt(y)) ch[z][ty] = x; ch[y][tx] = ch[x][tx ^ 1], fa[ch[x][tx ^ 1]] = y; ch[x][tx ^ 1] = y, fa[y] = x, fa[x] = z; // 画图后很好理解 push_up(y); push_up(x); } void splay(int x) { lazytag(x); while(!isrt(x)) { int y = fa[x], z = fa[fa[x]]; if(!isrt(y)) { if((ls(z) == y) == (ls(y) == x)) rotate(y); // 全左和全右转父亲复杂度更优 else rotate(x); // 非全左或全右转自己更优 } rotate(x); // 转两次 } } int access(int x) { for(int lst = 0; x; lst = x, x = fa[x]) { splay(x); rs(x) = lst; push_up(x); if(!fa[x]) break; } return x; // splay 的根 } int find(int x) { access(x); splay(x); while(ls(x)) x = ls(x); splay(x); // 转回去可以减小常数 return x; } public: void makeroot(int x) { access(x); splay(x); tag[x] ^= 1; swap(ls(x), rs(x)); } void link(int u, int v) { if(find(u) == find(v)) AC; makeroot(u); fa[u] = v; } void cut(int u, int v) { if(find(u) != find(v)) AC; makeroot(u); access(v); splay(v); if(ls(v) == u) { ls(v) = 0; fa[u] = 0; push_up(v); } } } ds;