第 7 章 · 02 杂项难点精讲:莫队/插头DP/LCT ★

第 7 章 · 02 杂项难点精讲:莫队/插头DP/LCT ★

本节定位：对应 OI Wiki docs/misc/mo-algo.md（莫队）、docs/misc/plug-dp.md（插头 DP）、docs/ds/lct.md（LCT）。难度：高阶（省选/IOI）。前置依赖：状压 DP（第 5 章）、平衡树 Treap/Splay（第 3 章）、分块（基础）。本节是难点精讲节（★），对三个省选级难点做 Wiki 之外的慢节奏讲解，不重写 Wiki。OI Wiki 自带 docs/contest/roadmap.md 有学习路线图，本节在其上做增量。

⚠️ 注意：这三个是省选/IOI 的"分水岭"算法，各自独立，难度都接近顶峰。建议一次只啃一个，不要并行。本节按"莫队 → 插头 DP → LCT"顺序精讲，每个都有"为什么难 / 慢节奏精讲"。

莫队算法（docs/misc/mo-algo.md）

为什么难

莫队的"难"很特别：单看代码像暴力，但它确实是 O(n√n)。这种"看似暴力实则分治"的反直觉，让人很难相信它是对的。难在理解"为什么指针乱跑的总复杂度是 O(n√n)"。

慢节奏精讲

问题场景：给一个序列，多次询问"区间 [l, r] 内某种统计值"（如不同颜色数、区间平方和），没有高效的在线结构，但区间能 O(1) 增量维护（加/减一个元素）。

核心思想：用两个指针 L、R 在序列上移动，维护当前 [L, R] 的答案。每次把 L、R 移到查询的 l、r，边移边更新答案。

关键技巧——离线排序：把所有查询按（左端点所在块，右端点）排序。分块大小取 √n，则：

• 左端点在同一块内时，L 在块内移动，每次 O(√n)；块间跨块 O(√n)。
• 同一块内，R 按右端点递增，单调不回退，总移动 O(n)；跨块时 R 回退一次 O(n)。

总复杂度：左指针 O(n√n)，右指针 O(n√n)，合计 O(n√n)。

变种

• 带修莫队：加一维"时间"，三元组 (左块, 右块, 时间) 排序，块大小 n^(2/3)。
• 树上莫队：用欧拉序把树上路径转成序列区间。
• 回滚莫队：当"删除"操作不好维护（只支持加入）时，按左端点块排序，对每块用"滚回右端点"的技巧。

插头 DP（docs/misc/plug-dp.md）

为什么难

插头 DP 是状压 DP 的极致：状态编码极抽象。要在"轮廓线"上记录每个位置是否有"插头"以及"插头的连通性"，编码方式（括号表示法）初看像天书。它属于"看懂定义就劝退"的算法。

慢节奏精讲

问题场景：在网格上求"经过所有格子的回路/路径方案数"（如多米诺骨牌铺满、哈密顿回路）。

逐格 DP：从左上到右下逐格转移，每个格子的状态由它上方和左方的边界（叫轮廓线）决定。

轮廓线与插头：轮廓线是当前已处理区域与未处理区域的分界线。轮廓线上每个位置可能有一个"插头"（表示这条边有路径穿过）。插头要记录两件事：

1. 有没有插头（有/无）。
2. 连通性：哪些插头互相连通（最终要形成回路，不能提前成环）。

括号表示法：在轮廓线上，同一连通分量两端的插头分别记成左括号 ( 和右括号 )，无插头记 0。于是状态是一个三进制（或四进制）的串，状压成一个整数。

经典题：多米诺骨牌铺满、求网格图的哈密顿回路方案数（Ural 1519）。

⚠️ 注意：插头 DP 的前置是状压 DP（第 5 章 · 01 节），状态压缩、位运算这些基础必须先牢。括号表示法没有捷径，必须对着 Wiki 的图一格一格手推小例子。

LCT（docs/ds/lct.md）

为什么难

LCT（Link-Cut Tree，动态树）把两个高难度结构揉在一起：实链剖分 + Splay 平衡树。光 Splay 就够难（第 3 章），还要在上面套"实链/虚链"的剖分思想，概念密度极高。

慢节奏精讲

问题场景：维护一个动态森林——支持 link（连边）、cut（断边）、查询两点连通/路径信息，边会动态增删。普通树剖（重链剖分）只适用于静态树，LCT 解决动态。

核心思想——实链剖分：把树剖成若干条"实链"，每条实链用一个 Splay 平衡树维护（按深度为关键字）。实链之间用"虚边"连接，虚边只从子链的 Splay 根指向父链的某个节点（认父不认子）。

核心操作——access(x)：把 x 到根的路径全部变成实链，使 x 和根在同一棵 Splay 里。所有其他操作都建立在 access 之上：

• makeroot(x)：换根，让 x 成为整棵树的根（access + splay + 翻转）。
• link(x, y)：连边（makeroot(x) 后把 x 的父指针指向 y）。
• cut(x, y)：断边（makeroot(x) + access(y) 后断开）。
• 查询路径：makeroot + access 后，路径信息就在一棵 Splay 里，直接读根节点维护的值。

前置：Splay 平衡树（docs/ds/splay.md）是硬前置，不懂 Splay 的旋转和懒标记，LCT 一定学不动。建议先彻底掌握 Splay，再学 LCT。

常见误区

1. 莫队分块大小取错：标准莫队块大小 √n，带修莫队 n^(2/3)，取错复杂度会退化。
2. 莫队忘记奇偶排序优化：左端点在奇数块时右端点升序、偶数块时降序，常数能减半，比赛必加。
3. 插头 DP 括号编码写错：左/右括号、无插头用 0/1/2，状态哈希极易出 bug，建议小例子验证。
4. LCT 忘记 pushdown/pushup：Splay 操作前后必须下放懒标记、更新维护值，顺序错了全错。这是 LCT 最常见的 RE/WA 来源。
5. LCT 的 access 没写全：access 涉及多次 splay + 换右儿子，少一步就错。务必对照 Wiki 代码逐行理解。

练习建议

• 莫队：P1494 [国家集训队] 小 Z 的袜子（区间选两同色概率），经典模板题。进阶：带修莫队 P1903。
• 插头 DP：P5056 [模板] 插头 DP（多米诺/回路），先过模板再练变种。
• LCT：P3690 [模板] Link Cut Tree（动态森林，link/cut/路径异或和）。
• 学法：三个算法各自独立，建议一个一个突破：莫队最易上手（先学），插头 DP 和 LCT 都需要前置扎实，留到冲刺阶段。
• 配合 docs/contest/roadmap.md：OI Wiki 自带的学习路线图覆盖了这些难点，建议结合本节和路线图制定复习计划。

💡 学习提示：这三个算法都是"会了就是省选分水岭"的存在。莫队性价比最高（思路清晰、模板短），建议先拿下；插头 DP 和 LCT 属于"备弹"，时间不够时优先保证前面的数据结构/图论/DP/String 基础。

本节要点

• 莫队：离线区间查询，按（左块，右端点）排序 + 双指针，分块 √n，总复杂度 O(n√n)；变种有带修/树上/回滚莫队。
• 插头 DP：状压 DP 极致，逐格 DP，轮廓线记录插头有/无 + 连通性，括号表示法编码，前置状压 DP。
• LCT：动态森林，实链剖分 + Splay，核心是 access（x 到根变实链），makeroot/link/cut 都建立在 access 上，前置 Splay。
• 三者独立，建议莫队先行，插头 DP 和 LCT 留冲刺；练习 P1494 / P5056 / P3690。
• 深入见 docs/misc/mo-algo.md、docs/misc/plug-dp.md、docs/ds/lct.md，配合 docs/contest/roadmap.md。