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\) 到树根变成实链。