# 1. Cartesian Tree 在数组上的 O(n) 构造中单调栈实现。 A 单调栈构造笛卡尔树复杂度 O(n log n) B 笛卡尔树可以 O(n) 构造，弹栈节点成为新元素的左子树 ✓ 正确答案 C 构造完成后右链不再有意义 D 笛卡尔树不保证中序为原数组顺序
# 2. Cartesian Tree 与直方图最大矩形中每个节点的子树对应一段以该高度为最小值的区间，单调栈构造后如何 O(n) 求解 A 笛卡尔树与最大矩形问题无关 B 直方图最大矩形必须 O(n log n) C 小根笛卡尔树中节点 u 的子树区间内所有值不小于 a[u]，枚举 a[u]×size(u) 可得最大矩形 ✓ 正确答案 D 最大矩形的高度一定是直方图最大值
# 3. bitset 优化背包与可达性中状态压缩成位集后每步转移 O(W/64)，哪些 DP 结构适合、何时退化 A 0/1 背包可达性用 dp |= dp<<w 转移，复杂度 O(nW/64)，但不支持计数与方案回溯 ✓ 正确答案 B bitset 背包可同时给出方案计数 C bitset 背包能处理浮点容量 D bitset 背包比布尔 DP 慢
# 4. Myers 的 bit-parallel O(nd/w) 编辑距离算法推导。 A Myers 算法复杂度 O(nm) 与普通 DP 相同 B 位并行编辑距离不支持近似匹配 C Myers 算法能直接输出最优编辑路径 D Myers 位并行用 P/M 位向量与 Peq 掩码按对角线推进，复杂度 O(nd/w)，d 为编辑距离 ✓ 正确答案
# 5. Rope（splay 树版）字符串拼接的 O(log n) 复杂度证明。 A Rope 拼接是 O(n) 的 B Rope 的内存是 O(n log n) C Rope 只能支持拼接 D Rope 用平衡树组织字符串，拼接/分裂均摊 O(log n)，证明依赖 splay 的势能分析 ✓ 正确答案
# 6. Bitset DP 在子集枚举（O(3^n)）与斯坦纳树上的工程应用。 A 子集枚举总量 O(3^n)，bitset 只对可向量化为位运算的聚合有加速，SOS 处理 min/max 类前缀聚合 ✓ 正确答案 B SOS DP 能把任意子集枚举降到 O(2^n) C 斯坦纳树可以完全避免子集枚举 D bitset 可加速任何 DP 转移
# 7. std::bitset 的工程实现中移位与按位运算复杂度 O(n/64)，count/any 如何用 SIMD 加速 A std::bitset 的按位运算复杂度 O(N) 按位循环 B std::bitset 以 64 位字数组存储，移位跨字搬移、count 用 POPCNT/SIMD，操作复杂度 O(N/64) ✓ 正确答案 C bitset 的 count 必须逐位循环 D bitset 无法用 SIMD 加速
# 8. AMS 估计 F2 中 4-wise independent hash 与 median trick 的组合推导。 A AMS 用 4-wise 独立哈希累加随机符号，E[X²]=F2，多副本中位数把成功率放大到高概率 ✓ 正确答案 B AMS 需要完全随机哈希才能估计 F2 C AMS 直接输出精确 F2 D AMS 的空间复杂度与 1/ε 成线性
# 9. Cartesian Tree 作为 RMQ ↔ LCA 等价性的桥梁证明。 A 笛卡尔树证明中 LCA 不保证下标落在区间内 B RMQ 与 LCA 的等价只在满二叉树时成立 C 笛卡尔树中序按下标、堆序按值，故 [l,r] 最值节点恰为 l 与 r 的 LCA，构成 RMQ↔LCA 的 O(n) 桥梁 ✓ 正确答案 D 该桥梁需要 O(n log n) 构造
# 10. AMS F∞ 估计的诚实性与有偏性证明。 A AMS F∞ 估计永远高估 B AMS F∞ 估计取随机位置统计该值出现次数，期望恰为 F∞（无偏），方差大需多副本取中位数 ✓ 正确答案 C 诚实估计器一定有界方差 D F∞ 无法用流算法估计
# 11. Misra-Gries 与 Count-Min 在不同 cardinality 下的工程基准对比。 A Count-Min 提供确定性误差界 B Misra-Gries 保证估计值 ≥ f-εn（确定性），Count-Min 保证误差 ≤ε||f||₁ 且失败率 ≤δ（随机化） ✓ 正确答案 C Misra-Gries 需要 O(log(1/δ)) 因子空间 D 两者都不能做频率估计
# 12. Misra-Gries 在 Space-Saving（MG-Space Saving）的等价变换。 A Space-Saving 的误差界比 Misra-Gries 差一个 log B Space-Saving 与 Misra-Gries 的估计下界相同，SS 用"顶替 + 继承"替代"全体减一" ✓ 正确答案 C Space-Saving 不能保证前 K 名不漏报 D 两者空间复杂度不同阶
# 13. Misra-Gries 算法的 counter decrement 过程与 (k-1)/k 频率下界保证。 A MG 中每次"全体减一"与一个新元素出现配对，总流失 ≤ n/(K+1)，故估计 ≥ f - n/(K+1) ✓ 正确答案 B MG 的估计误差可以任意大 C MG 只对 heavy hitter 有效但无界保证 D MG 计数器越多误差越大
# 14. Rope 在文本编辑器（Xerox PARC 原版）vs Gap Buffer 的取舍。 A Gap Buffer 适合大跨度随机编辑 B Gap Buffer 支持任意位置 O(1) 编辑 C Rope 的拼接是 O(长度) D Rope 用平衡树组织字符串，任意位置编辑与拼接 O(log n)，但节点开销大；Gap Buffer 适合光标局部编辑 ✓ 正确答案
# 15. Shift-And / Shift-Or 算法的位并行实现中 n × m / 64 优化。 A Shift-And 只能匹配单个字符模式 B Shift-And 需要预处理文本 C Shift-And 每字符转移 D=((D<<1)|1)&B[ch]，复杂度 O(n·m/64)，m≤字长时 O(n) ✓ 正确答案 D Shift-And 复杂度 O(nm) 与朴素相同
# 16. 为什么 Count-Min 不能直接做 min/max/median 查询。 A Count-Min 与 GK 草图解决的问题相同 B Count-Min 可以通过遍历矩阵做 median C Count-Min 能精确回答任意点查询 D Count-Min 只估计频率上界，不含值的序/极值信息，故不能直接做 min/max/median，后者需分位数草图 ✓ 正确答案
# 17. 为什么位并行在中英文混合模式匹配中通常不如 AC + 高效实现？ A 位并行在中英文下依然最优 B 中英文混合下位并行需处理变长编码与超大掩码表，AC 自动机按字典树一次扫描、与编码解耦，通常更优 ✓ 正确答案 C AC 自动机复杂度 O(nm) D UTF-8 中文是单字节编码
# 18. 保守更新（conservative update）变体如何减少过估计的具体工程实现。 A 保守更新把插入时的 d 个桶全部 +1 B 保守更新会破坏频率上界保证 C 保守更新只递增等于当前最小计数的桶，保持上界不变量且减少过估计 ✓ 正确答案 D 保守更新只适用于 Bloom Filter
# 19. BNDM（Backward Nondeterministic Dawg Matching）的位并行设计与 cut-the-rope trick。 A BNDM 必须逐字符扫描整个文本 B BNDM 从窗口尾部向左扫描并维护后缀匹配位向量，位向量归零即剪断窗口（cut-the-rope） ✓ 正确答案 C BNDM 不需要预处理模式 D BNDM 位向量为 0 时仍需扫完窗口
# 20. bitset 化传递闭包中 Floyd-Warshall 的按行位或如何把 O(n³) 降到 O(n³/64) A bitset 传递闭包按 k 迭代、A[i]|=A[k] 按位或，复杂度 O(n³/64) ✓ 正确答案 B bitset 优化后复杂度 O(n²) C 按位或会破坏 Warshall 的正确性 D 该优化只能用于稠密图
