# 1. 1D / 1D DP 在单调栈与二分线段树混合的工程实现。 A 用单调栈维护候选集，配合二分线段树快速定位最优转移，实现 O(n log n) ✓ 正确答案 B 单调栈无法用于 DP 优化 C 二分线段树不能查询最优 D 1D/1D DP 只能 O(n²)
# 2. 1D / 1D 动态规划在分治优化、Aliens Trick、Knuth 优化的取舍。 A 分治优化用单调决策点批量计算，Aliens Trick 用惩罚系数处理段数约束 ✓ 正确答案 B Knuth 优化要求决策点随机 C Aliens Trick 不涉及二分 D 三者都不依赖决策单调性
# 3. Quadtree 在图像处理与 GIS 索引的 O(n log n) 区域查询。 A 查询不进行剪枝 B 四叉树查询总是 O(n) C 它无法用于图像处理 D 沿树剪枝不相交区域、整块返回包含区域，实现高效范围查询 ✓ 正确答案
# 4. 李超线段树（Li Chao Tree）如何在 O(log n) 内插入直线并查询 x 处最大值，与凸包或单调栈的适用差异？ A 李超树插入是 O(n) B 李超树只能查询最小值 C 凸包/单调栈支持任意顺序插入 D 李超树支持任意顺序插入直线与任意 x 查询 O(log n)，凸包/单调栈要求单调性 ✓ 正确答案
# 5. 线段树分治在区间修改的离线加回溯的 O(n log² n) 推导。 A 区间修改只落一个节点 B 复杂度为 O(n) C 每个区间修改落到 O(log n) 个节点，结合每节点 O(log n) 操作，总 O(n log² n) ✓ 正确答案 D 无法回溯
# 6. Klee's Algorithm 在区间并长度的 O(n log n) 工程实现。 A 需要 O(n²) 两两判断 B 无需排序端点 C 排序端点后用扫描线维护覆盖层数，累加覆盖长度，O(n log n) ✓ 正确答案 D 无法处理区间并
# 7. 二维线段树在矩阵区域和与区域最值的 O(n log² n) 推导。 A 区域查询是 O(n) B 外层 x 分解 O(log n) 节点、内层 y 查询 O(log n)，区域查询 O(log² n) ✓ 正确答案 C 它只有一个维度 D 内存是 O(n)
# 8. 矩形覆盖在 union-find 与离散化的 O(n α(n)) 优化。 A 并查集无法跳跃 B 每个格子被重复填充 C 用并查集跳到下一个未覆盖位置，每格只处理一次，总 O(n α(n)) ✓ 正确答案 D 复杂度为 O(n²)
# 9. 线段树分治在维护可撤销并查集与 segment tree 节点遍历。 A 用按秩合并 + 操作栈记录修改，DFS 退出时按后进先出撤销，不用路径压缩 ✓ 正确答案 B 可撤销并查集用路径压缩 C 撤销顺序任意 D 无法记录合并修改
# 10. 线段树分治加可撤销并查集中回溯顺序必须严格后进先出，按秩合并如何支持撤销？ A 撤销顺序任意 B 撤销必须严格后进先出，按秩合并记录修改到栈支持逆序回滚 ✓ 正确答案 C 可撤销并查集用路径压缩 D 按秩合并不支持撤销
# 11. 线段树套线段树在二维区间 K-th number 的 O(log² n) 推导。 A 查询复杂度是 O(n) B 只需一层线段树 C 无法处理二维 K-th D 树套树按值域与位置分层，值域二分 + 内层计数实现 O(log² n) 查询 ✓ 正确答案
# 12. Boost Geometry R-tree 在空间索引的工程接口。 A 它只能存点 B 提供 query 接口支持 intersects/nearest 等空间查询，基于 MBR 组织 ✓ 正确答案 C 不支持批量加载 D 无剪枝机制
# 13. 树套树在矩形第 K 大与矩形不同元素数的离线持久化工程实现。 A 无法离线处理 B 不同元素数用 last 位置技巧是错的 C 离线按坐标排序 + 前缀差分 + 树套树计数，实现矩形第 K 大/不同元素数 ✓ 正确答案 D 复杂度为 O(n)
# 14. 树状数组套主席树在动态 K-th 的 O(log² n) 维护工程实现。 A 树状数组按位置更新、主席树按值域计数，动态区间 K-th 每次 O(log² n) ✓ 正确答案 B 只能处理静态 C 内存是 O(n) D 更新复杂度为 O(n)
# 15. 树状数组套平衡树在动态区间排名与前驱后继查询工程实现。 A 复杂度为 O(n) B 只支持静态 C 前驱后继无法查询 D 位置分块 + 值域平衡树，区间拆 O(log n) 块各 O(log n) 查询，总 O(log² n) ✓ 正确答案
# 16. Segment Tree Beats 的势能分析中区间取 max/min/加这类操作为何总复杂度 O((n+q) log² n)？ A 势能可以无限增长 B 每次操作都是 O(log n) 最坏 C 用最大/次大值区分度作势能，势能单调下降且有界，总复杂度 O((n+q) log² n) ✓ 正确答案 D 复杂度为 O(n²)
# 17. CF 813E 在线段树分治与持久化数据结构的工程实现。 A 无法用持久化结构 B 用 last 位置法把出现次数约束转化为阈值，主席树按位置前缀查询 O(log n) ✓ 正确答案 C 复杂度为 O(n²) D 与出现次数无关
# 18. CF 848C 在线段树分治的贡献拆解与离线 add 和 erase 工程实现。 A 无法离线处理 B 贡献无需拆解 C 贡献拆解 + 线段树分治按时间 add/erase，离线维护区间贡献 ✓ 正确答案 D 复杂度为 O(n)
# 19. CF 896E 在区间染色与区间减一与区间求和的工程实现。 A 用势能线段树维护最大值/次小值/计数，配合懒标记处理染色与减一 ✓ 正确答案 B 普通懒标记即可处理 C 无需维护次小值 D 复杂度为 O(n) 每次
# 20. KD-Tree 在 CGAL Kd-Tree 的静态与增量构建取舍。 A 静态构建不平衡 B 增量构建永远平衡 C 静态构建用中位数分割保证平衡，增量构建支持动态插入但可能退化 ✓ 正确答案 D 两者查询性能相同
# 21. KD-Tree 在 K 维最近邻查询的 O(2^d n^(1-1/d)) 推导。 A 高维时剪枝更有效 B 高维时查询更快 C 平均 O(2^d n^(1-1/d))，高维时剪枝失效退化为线性扫描 ✓ 正确答案 D 复杂度与维数无关
# 22. Quadtree 与 KD-Tree 在 2D 区域查询的取舍。 A Quadtree 总是优于 KD-Tree B Quadtree 固定四分、适合均匀分布，KD-Tree 中位数分割、自适应非均匀点 ✓ 正确答案 C KD-Tree 固定划分 D 两者划分方式相同
# 23. 二维线段树与持久化在矩阵历史版本的工程实现。 A 无法查询历史版本 B 每个版本重建整棵树 C 内存与版本数无关 D 修改复制路径节点、共享未变部分，支持 O(log² n) 历史版本查询 ✓ 正确答案
# 24. 二维线段树在 KD-Tree 退化与四叉树的取舍。 A 二维线段树固定分裂保证稳定 O(log² n) 但内存大，KD-Tree 数据自适应可能退化 ✓ 正确答案 B 二维线段树比 KD-Tree 更省内存 C KD-Tree 查询最坏也 O(log² n) D 四叉树永不退化
# 25. 二维线段树在四叉树分块与扫描线的混合维护工程实现。 A 四叉树分块支持局部更新，扫描线按事件顺序处理，适合动态区域统计 ✓ 正确答案 B 扫描线与分块无关 C 分块无法更新 D 混合方案内存比二维线段树更大
# 26. 二维线段树在外部存储（External Memory）的工程实现。 A 用 B-tree 式高扇出与页面局部性减少磁盘 IO，磁盘场景常选 R-tree/B-tree ✓ 正确答案 B 磁盘 IO 不是主要成本 C 内存线段树直接适用磁盘 D 无需考虑页面局部性
# 27. 决策单调性在四边形不等式与 SMAWK 算法的判定工程实现。 A SMAWK 是 O(n²) B 四边形不等式与决策单调性无关 C 四边形不等式是决策单调性的充分条件，SMAWK 在 Monge 矩阵上 O(n) 求最优决策 ✓ 正确答案 D 决策单调性无法判定
# 28. 区间 chmin 与 chmax 在 max、second max、count 三元组工程实现。 A 维护 max/second max/count 使 chmin 只需改最大值 O(1)，非此才递归 ✓ 正确答案 B 只需维护最大值即可 C count 信息无用 D chmin 必须递归到叶子
# 29. 区间 chmin 与 chmax 的势能 O(n log² n) 严格证明。 A 势能可无限增长 B 以最大-次大差异为势能，单调下降且有界，均摊 O((n+q) log² n) ✓ 正确答案 C 每次操作最坏 O(n) D 无法证明均摊复杂度
# 30. 扫描线与线段树在矩形面积并的 O(n log n) 工程实现。 A 线段树只维护最值 B 扫描线按 x 排序事件，线段树维护 y 覆盖长度，累加得面积，O(n log n) ✓ 正确答案 C 无需离散化 D 需要 O(n²)
# 31. 扫描线在 Segment Tree on Tree 的 O(n log² n) 路径查询。 A HLD 拆路径为 O(log n) 链区间，线段树 O(log n) 维护，总 O(log² n) ✓ 正确答案 B 路径查询是 O(n) C 无需拆链 D 复杂度为 O(log n)
# 32. 扫描线在矩形周长并的下边长、上边长、左右边长统一推导。 A 垂直边用覆盖长度计算 B 周长只需水平边 C 水平边 = 扫描线覆盖长度变化量，垂直边 = 覆盖层数非零段长度，统一累加 ✓ 正确答案 D 无法用扫描线求周长
# 33. 洛谷 P6242 在区间取最值与区间求和与区间历史和的复合操作。 A 用势能线段树维护 max/min/second/count 多套标记，并处理历史最大值的传播 ✓ 正确答案 B 普通懒标记即可 C 无需历史标记 D 复杂度为 O(n) 每次
# 34. 矩形面积并的三维拓展在体积并的工程实现。 A 无需维护覆盖层数 B 与二维面积并复杂度相同 C 只需一维扫描 D 外层 z 扫描 + 内层二维面积并，复杂度 O(n² log n) ✓ 正确答案
# 35. 离线与在线混合的线段树维护 DP 在分治 FFT 配合工程实现。 A 卷积无法优化 B FFT 不用于卷积 C 分治 FFT 是 O(n²) D 分治统计跨界贡献 + FFT 卷积，优化卷积型 DP 到 O(n log² n) ✓ 正确答案
# 36. 线段树分治在动态图连通性 offline 的工程实现。 A 用普通并查集即可 B 无法离线处理 C 复杂度为 O(m) D 边按时间区间插入线段树节点，DFS 施加/撤销（可撤销并查集），离线回答连通性 ✓ 正确答案
# 37. 线段树分治在图论二分性约束的离线判定工程实现。 A 普通并查集即可判定二分 B 无法离线 C 用带权可撤销并查集维护奇偶性，边按时间区间插入子树，离线判定各时刻二分 ✓ 正确答案 D 复杂度为 O(m)
# 38. 线段树套 Splay 在区间翻转与区间插入的工程实现。 A 只需外层线段树 B Splay 提取区间实现翻转/插入，外层线段树按位置组织以支持值域查询 ✓ 正确答案 C Splay 无法处理区间翻转 D 树套树用于单维区间
# 39. Segment Tree Beats 的适用条件中需要维护"次大值/次小值"与"最大/最小出现次数"的节点信息？ A 次大值用于区间加 B 只需维护最大值 C count 信息无用 D 次大值/出现次数使 chmin 能判定"只改最大值"的 O(1) 分支，是势能分析前提 ✓ 正确答案
# 40. 区间取模（区间 mod x）为什么能被势能分析约束，每个数取模后至多减半，总操作次数 O((n+q) log A) 的直觉？ A 复杂度为 O(n²) B 每个数取模后至少减半，更新次数 O(log A)，总复杂度 O((n+q) log A) ✓ 正确答案 C 每个数可取模 O(n) 次 D 取模不减半
# 41. Segment Tree Beats 在 lazy 势能分析的双势能标记工程实现。 A 标记传播顺序无关 B 只需一套懒标记 C 双势能无法复合 D chmin 与 chmax 各用一套懒标记分别影响 max/min，传播需按优先级保证势能单调 ✓ 正确答案
# 42. Segment Tree Beats 在势能线段树与吉司机线段树统一框架。 A 吉司机线段树不维护次大值 B 两者是同一框架，核心是次大值分支 + 势能分析保证均摊复杂度 ✓ 正确答案 C 两者是不同算法 D 吉司机线段树与势能无关
# 43. Segment Tree Beats 在维护区间最大、次大与计数的三元组标记。 A cntMax 不用维护 B (max, secondMax, cntMax) 使 chmin 能 O(1) 计算"只改最大值"的和变化 ✓ 正确答案 C 三元组只需 max D 三元组用于范围之外
# 44. 区间历史最值与历史和的 Segment Tree Beats 拓展工程实现。 A 历史最值无需传播 B 只需当前懒标记 C 增加历史懒标记记录历史峰值，push 时用历史标记更新子节点历史最值 ✓ 正确答案 D 历史标记与当前标记无关
# 45. Segment Tree Beats 与普通懒标记线段树的边界中哪些操作仍需 O(log n) 单次而非势能均摊？ A 所有操作都势能均摊 B 区间加也需递归 C chmin 每次最坏 O(log n) D 区间加/赋值/求和仍 O(log n) 单次，取最值则势能均摊 ✓ 正确答案
# 46. 扫描线求矩形面积并中为什么用 y 轴离散化加线段树维护覆盖次数，覆盖计数与区间求和的区别？ A 无需离散化 B 覆盖长度等于层数之和 C 线段树维护区间和即可 D 覆盖长度 = 层数>0 的区间长度，与"层数求和"不同，需特殊维护非零判定 ✓ 正确答案
