# 1. DSU on Tree 在子树众数计数 (CF 600E Lomsat gelral) 的 O(n log n) 重儿子保留策略。 A 每个节点作为轻子树成员被重复统计的次数为 O(log n)，故总复杂度 O(n log n) ✓ 正确答案 B 重儿子子树统计完成后必须立即清空桶 C DSU on Tree 依赖并查集的路径压缩来保证复杂度 D 重儿子保留策略使每个节点在整个过程中恰好被统计一次
# 2. 势能线段树的核心思想中区间取模/开方/整除等"值快速减小"操作如何用势能证明总复杂度？ A 区间取模时，若区间最大值小于模数则可直接剪枝返回 ✓ 正确答案 B 势能函数 Φ 随每次有效取模操作严格增加 C 势能线段树要求所有操作都不能打 lazy 标记 D 区间取模的摊还复杂度与值域 A 无关
# 3. 路径赋值 + 路径求和的双 lazy 标记下推顺序中赋值标记覆盖求和标记，下推时先赋值后求和 A 赋值标记和求和标记可以合并成一个懒标记 B 下推时应先下推求和标记，再下推赋值标记 C 下推赋值标记时需清空儿子的求和标记，再下推求和标记 ✓ 正确答案 D 赋值操作会累加到旧有求和标记之上
# 4. CF 1648D 的 STB 离线约束实现 (区间 chmin 矩阵 + 多次询问) 工程细节。 A STB 的 chmin 操作需要把整个区间暴力下放到叶子 B 离线处理时按约束右端点排序，可把区间约束转化为扫描线上的 chmin 与查询 ✓ 正确答案 C 区间 chmin 与区间 max 查询的标记可以合并为单个 add 标记 D 该题中矩阵乘法使用普通实数乘法即可
# 5. STB 在 lazy 标记合并的 Φ 增量和 O(1) push_down 复杂度。 A 每次 push_down 需要递归访问整个子树 B 势能 Φ 定义为节点"最大值与次大值之差"时，有效 chmin 使该节点势能严格下降 ✓ 正确答案 C lazy 标记合并会使势能按 O(log n) 幅度整体上升 D STB 的摊还分析依赖于随机化输入
# 6. STB 在区间 add 操作时 Φ 的递推证明与 O(log n) 摊还代价。 A 区间加会改变节点内最大值与次大值之差 B 差值型势能在整体区间加下保持不变，故区间加只带来 O(log n) 的势能回补 ✓ 正确答案 C 区间加的摊还代价与区间长度成正比 D STB 不支持区间加与 chmin 同时存在
# 7. 离线区间最大子段和的 Segment Tree Beats 在区间合并的 O(n log n) 推导。 A 最大子段和合并时 pref = l.pref 恒成立 B 离线扫描右端点并用线段树维护所有左端点的候选值，可将区间询问降为 O(n log n) ✓ 正确答案 C STB 无法用于最大子段和问题 D 区间加操作必须暴力更新到叶子
# 8. 经典势能线段树题中区间开方、区间取模、区间 gcd 变化次数分析？ A 区间取模的剪枝条件是区间最大值小于模数 m ✓ 正确答案 B 对任意 a 与 m，恒有 a mod m ≥ a/2 C 区间开方一次最多改变 O(1) 个节点的值 D 区间 gcd 问题的势能与值域大小无关
# 9. HLD 与虚树（Virtual Tree）在多关键点查询中的配合中先按 dfn 排序再建虚树，HLD 维护路径信息 A 虚树必须保留原树所有节点 B 虚树的边权等于两端点的 dfn 之差 C 构造虚树需将关键点按 dfn 序排序，并用相邻点的 LCA 补全节点集 ✓ 正确答案 D 建虚树后只能做子树操作，不能做路径操作
# 10. DSU on Tree 在 NOI、IOI 的工业级实现。 A 清空子树贡献时应直接对桶数组整体 memset 为 0 B DSU on Tree 的空间复杂度为 O(n log n) C 重儿子子树统计完也必须清空桶 D 使用 dfn 序区间遍历子树可替代递归逐点收集，降低常数 ✓ 正确答案
# 11. DSU on Tree 在维护子树深度与祖先数的工程实现。 A DSU on Tree 只能统计众数类信息 B 树状数组版 DSU on Tree 的总复杂度仍为 O(n log n) C 深度桶需要像颜色桶一样做离散化 D 当查询需要"深度区间内节点数"时，可用树状数组作为桶实现前缀求和 ✓ 正确答案
# 12. HLD 在 NOI、HDU 3966 的工业级模板。 A 边权转点权时，边权应挂在深度较小的端点上 B 重链上的 dfn 序是连续的，因此路径操作可拆成 O(log n) 个线段树区间 ✓ 正确答案 C HLD 预处理只需一次 DFS D 路径查询时无需处理 LCA 的特殊情况
# 13. 换根（reroot）场景下 HLD 的失效原因与替代方案中 HLD 基于固定根的重链剖分，换根后重儿子变化需 LCT 或欧拉序+线段树 A HLD 换根后只需重新计算 top 数组即可继续使用 B 需要动态换根与路径修改时必须使用欧拉序+线段树 C 换根到 r 后，若 u 是 r 的祖先，则 u 的子树对应原欧拉序的区间补集 ✓ 正确答案 D LCT 的 makeroot 操作与 splay 无关
# 14. CF 1692G 2^k 子段数查询的 STB 实战与边界条件。 A 该问题必须用 STB 的 chmin 操作才能求解 B 单点修改只会影响一个相邻布尔量 C 条件 a[i] < 2·a[i+1] 可以直接用 int 相乘判断而不必担心溢出 D 满足条件的相邻关系可转化为布尔量，再统计长度为 k 的连续全 1 段 ✓ 正确答案
# 15. CF 438D The Child and Sequence 的区间取模与单点修改 STB 工程实现。 A 区间取模必须把区间内所有值逐个取模才能剪枝 B 该题需要维护最大值、次大值与最大值个数三个量 C 因任意 a mod x < a/2，每个值至多被有效取模 O(log A) 次 ✓ 正确答案 D 单点修改会使整体势能增加 O(n) 无法摊还
# 16. CF 896E Leaving the Bar 在区间染色 + 区间减一 + 区间求和的 STB 实战。 A 维护最大值、次大值与最大值个数，当 mx - x ≥ smx 时只需整段更新最大值段 ✓ 正确答案 B "大于 x 才减 x"的操作只能暴力递归到叶子，无法剪枝 C 该操作每次都会随机增加势能，无法保证摊还复杂度 D 查询区间内等于 x 的个数时，只需检查 x 与区间最小值的关系
# 17. STB 历史最值与历史和在 (max、smax、cmax、add) 四元组与 (maxh、smaxh、cmaxh、addh) 势能。 A 维护历史最值时不需要区分最大值段与其他段 B 下推时应先应用当前 add 标记，再应用历史 hadd 标记 C 历史最大值标记 hadd 记录的是节点挂起期间达到的最大加量 ✓ 正确答案 D STB 加历史标记后摊还复杂度退化为 O(n²)
# 18. STB 双势能标记 (max、second_max、count + add 势能) 的工程实现与正确性。 A 节点只需维护最大值即可完成所有 chmin 判断 B 最大值个数 cmx 只在查询时需要，不影响更新 C chmin 与 add 标记可以合并成单一标记 D 当 smx < x < mx 时，chmin 只需更新最大值段，复杂度 O(1) ✓ 正确答案
# 19. STB 在 10^5 区间 / 10^5 长度下的常数优化路径 (cache-friendly、循环展开)。 A STB 的常数瓶颈主要在算法复杂度而非实现细节 B 使用 long long 存所有字段能显著提升性能 C 递归实现无法做任何常数优化 D 把 mx、smx、cmx 等字段按结构体数组（SoA）布局可提升缓存命中率 ✓ 正确答案
# 20. HLD 在 Codeforces 161D、CF 165D 路径问题模板的实战。 A CF 165D 的边权修改需把边权映射到深度较大的端点再维护 ✓ 正确答案 B CF 161D 的距离计数问题可直接用 HLD 拆区间求解 C 点分治的复杂度为 O(n² log n) D HLD 适合聚合子树距离分布的问题
# 21. STB 在 ODT (Chtholly Tree) 与吉司机线段树的等价边界。 A ODT 的摊还复杂度对所有输入都成立 B STB 的势能分析不依赖数据随机性 ✓ 正确答案 C 区间赋值操作会使 STB 完全失效 D ODT 与 STB 在实现上完全等价
# 22. STB 在区间 chmin + chmax 复合的 Φ 单调性证明 (2D 势能函数)。 A 有效 chmin 会同时增大最小值侧的差值势能 B 2D 势能分别刻画"最大-次大差"与"次小-最小差"两个方向，两维互不创生 ✓ 正确答案 C chmin 与 chmax 复合时总势能无法界定 D 支持 chmax 只需维护最大值三件套即可
# 23. STB 在区间 chmin 操作时 Φ 的递减证明与 α 系数。 A 每次 chmin 递归访问都消耗 O(log n) 势能 B 势能初值与值域 A 无关 C α 系数越大，复杂度上界越紧 D 有效 chmin 使节点"最大值-次大值"差值至少减半，log 势能至少减 1 ✓ 正确答案
# 24. STB 在吉司机线段树与势能线段树的统一框架。 A 势能线段树要求操作必须能表达为区间赋值 B 统一框架的关键是"整段更新条件 + 势能函数"两个可配置点 ✓ 正确答案 C 取模与开方的剪枝条件完全相同 D 势能函数只能取"最大值-次大值之差"
# 25. STB 的势能 O(n log² n) 严格证明（Ji 论文）关键引理。 A 分层势能会使总界退化为 O(n²) B 有效 chmin 使差值至少加倍，层号上升 C Ji 论文的复杂度证明不依赖势能下降 D 分层势能按"差值所在的对数量级"把势能分摊到 O(log log A) 个层次 ✓ 正确答案
# 26. 势能函数的选取技巧中如何根据操作性质设计势能并证明总操作次数上界？ A 势能法只能用于线段树类数据结构 B 势能初值必须为 0 才能证明复杂度 C 温和操作回补势能越多越好 D 势能函数应从"操作导致某个量严格减小"的事实反推设计 ✓ 正确答案
