# 1. LCA 的倍增（binary lifting）算法中 up[k][v] 表如何构建，为什么查询时从大到小跳步，复杂度 O(log n)？ A 查询时应从小到大跳步才能保证正确 B 倍增表预处理复杂度是 O(n) C up[k][v]=up[k-1][up[k-1][v]] 且查询从大到小跳步，可保证 O(log n) 内求出 LCA ✓ 正确答案 D 跳步顺序不影响正确性，只是常数优化
# 2. 树上差分加 LCA 中如何用树上差分 O(n) 统计每条边或点被路径覆盖的次数？ A 点差分只需 cnt[u]++、cnt[v]++ 两个标记 B 树上差分统计每条路径需要 O(log n) 标记时间 C 边差分在 lca 处只需减一次 D 点差分在 lca 处 cnt[lca]--、在 parent[lca] 处再减一次，后序累加后 cnt[x] 即点 x 的覆盖次数 ✓ 正确答案
# 3. Schieber-Vishkin LCA 的 O(1) 查询中提升数组与重路径压缩。 A Schieber-Vishkin 通过 inlabel 位标记与 ascendant 重路径压缩实现 O(n) 预处理、O(1) 查询 ✓ 正确答案 B Schieber-Vishkin 的预处理与查询复杂度均为 O(log n) C Schieber-Vishkin 需要 O(n log n) 额外内存 D Schieber-Vishkin 比倍增法实现更简单
# 4. Sparse Table 的 O(n log n) 预处理 + O(1) 查询的位运算向量索引推导。 A 查询 [l,r] 用两个可重叠的长度 2^k 的区间合并，k=⌊log2(r-l+1)⌋，预处理 O(n log n)、查询 O(1) ✓ 正确答案 B Sparse Table 查询需要枚举区间内所有元素 C Sparse Table 支持区间求和 D Sparse Table 支持单点修改 O(log n)
# 5. ±1 RMQ 与一般 RMQ 的等价归约中笛卡尔树与 Euler Tour + LCA 的工程实现。 A 一般 RMQ 无法归约到 ±1 RMQ B 笛卡尔树的堆序按下标、中序按值 C 一般 RMQ 经笛卡尔树转 LCA，LCA 再经 Euler Tour 转 ±1 RMQ，两条归约均为 O(n) 构造 ✓ 正确答案 D Euler 序深度序列的相邻差可以是任意整数
# 6. Fischer-Heun RMQ 块预处理的 4-ary 块划分与 O(1) 查询。 A Fischer-Heun 对每块单独预计算，预处理复杂度 O(n log n) B Fischer-Heun 不适用于 ±1 RMQ C Fischer-Heun 利用 ±1 块形态只有 O(√n) 种共享块内表，实现 O(n) 预处理、O(1) 查询 ✓ 正确答案 D Fischer-Heun 查询需要二分定位块
# 7. 带修改 Mo 队（Mo's algorithm with updates）的时间复杂度推导与实战取舍。 A 带修改 Mo 队的块大小取 √n 最优 B 带修改 Mo 队的时间复杂度与普通 Mo 相同 C 带修改 Mo 队不能处理修改操作 D 带修改 Mo 队维护 (l,r,t) 三指针，块大小 n^(2/3) 时总复杂度 O(n^(5/3)) ✓ 正确答案
# 8. Chtholly Tree 的 split、assign、merge 操作如何保证 O(n log n) 期望复杂度。 A ODT 在任意数据下每操作都是 O(log n) B ODT 的 assign 不需要先 split C ODT 用 set 维护值连续区间，split 与 assign 配合，在随机区间赋值数据下期望总复杂度 O(n log n) ✓ 正确答案 D ODT 只能处理区间赋值
# 9. Mo 树剖（LCA + 子树路径）的 Euler 序重排与块分割的工程实现。 A 树上 Mo 队直接把树拍成前序遍历序列 B 树上 Mo 队用进出两次的欧拉序把路径转成区间，出现奇数次的点构成路径，LCA 需单独处理 ✓ 正确答案 C 树上 Mo 队不需要欧拉序 D 树上 Mo 队每查询 O(log n)
# 10. Mo 队在 10^6 查询 / 10^5 数组上的常数优化中循环展开、寄存器利用。 A 奇偶排序会让 r 指针总移动量增大 B 奇偶（Zigzag）排序使 r 指针在块间折返移动，配合内联与数组化访问可大幅降低 Mo 队常数 ✓ 正确答案 C Mo 队常数只与块大小有关，与排序方式无关 D 10^6 查询下 Mo 队必须用分块重构替代
# 11. Mo 队算法的排序准则中块大小 B = n/√q 时 L1 移动次数最优的推导。 A 块大小 B 越大 l 指针移动越多、r 指针移动越少，B=n/√q 时总移动 O(n√q) ✓ 正确答案 B 块大小取 q 时最优 C Mo 队排序与块大小无关 D 总移动量恒为 O(nq)
# 12. 回滚 Mo 队（Rollback Mo's）处理不支持撤销操作的数据结构。 A 回滚 Mo 队依赖数据结构支持快速删除 B 回滚 Mo 队只能处理静态数组 C 回滚 Mo 队复杂度比普通 Mo 高一个 log D 回滚 Mo 队通过快照/撤销栈还原左端点的临时扩展，使数据结构只需支持 add ✓ 正确答案
# 13. 树上 Mo 队（Tree Mo）的 Euler 序与块分割。 A 树上 Mo 的区间内出现偶数次的点属于路径 B 树上 Mo 的块大小取 n C 树上 Mo 用长度为 2n 的欧拉序，路径由区间内出现奇数次的点构成，lca 需特判 ✓ 正确答案 D 树上 Mo 无法处理子树查询
# 14. ODT 与 Lazy Segment Tree 在彩色区间操作中的工程取舍。 A ODT 依赖随机区间赋值下的段数均摊，Lazy 线段树保证任意数据 O(log n) 且只支持可合并聚合 ✓ 正确答案 B ODT 在任何数据下都保证 O(log n) 每操作 C Lazy 线段树支持任意区间查询而 ODT 不能 D 两者都需要 O(n log n) 预处理
# 15. 静态 RMQ 转 LCA 中区间最值问题能转化为笛卡尔树上的 LCA 查询，欧拉序如何参与？ A 区间 [l,r] 的最值节点等于下标 l 与 r 在笛卡尔树上的 LCA，欧拉序把 LCA 化为深度 ±1 RMQ ✓ 正确答案 B 笛卡尔树的中序按值、堆序按下标 C RMQ 与 LCA 是两种完全无关的问题 D 笛卡尔树的构造复杂度是 O(n log n)
# 16. ODT 在 Codeforces 896C、CF 915E 的实际题面与解法对比。 A CF 915E 的数据保证 ODT 不退化 B ODT 可以解决任意区间操作问题 C CF 896C 由随机种子生成数据、ODT 均摊可行；CF 915E 数据非随机，线段树等最坏 O(log n) 结构更稳妥 ✓ 正确答案 D 两道题都必须用 ODT 才能通过
# 17. ODT 的最坏退化构造中有序输入时 O(n) 段全部分裂的反例。 A ODT 段数在任何数据下都不超过 O(log n) B ODT 的 split 操作最坏是 O(1) C 只要使用 set 实现，ODT 就不会退化 D 有序输入下 ODT 段数可增至 O(n) 且每次操作 O(n)，必须依赖随机数据下的合并均摊 ✓ 正确答案
# 18. 珂朵莉树在 random 数据下段数收敛到 O(n log n) 的概率证明。 A 随机模型下每次区间赋值使段数期望增加 B 段数收敛证明与概率无关 C 珂朵莉树段数收敛对任意输入都成立 D 随机区间赋值使段数期望呈负漂移，分支过程 + Chernoff 界可证总操作量 O(n log n) 高概率成立 ✓ 正确答案
# 19. Sparse Table 二维版本在 4 维稀疏表与分块的 O(1) 查询工程实现。 A 二维 Sparse Table 查询需要枚举子矩阵内所有元素 B 二维 ST 支持区间求和 C 二维 ST 预处理 O(nm log n log m)，查询用四个角子矩阵合并，O(1) 且仅支持幂等聚合 ✓ 正确答案 D 二维 ST 的预处理复杂度是 O(nm)
