树形构造与性能¶
结论与适用范围¶
特殊构造可以放大部分差异，但这些测量尚未找到能在“两倍标程时间、0.5 秒向上取整”的条件下可靠排除三份备用或并列实现的输入。
| 题目 | 针对性构造的结果 | 可以据此得出的结论 |
|---|---|---|
| 护林员 | 针对排序选主元的收益排列，在正式上限时约慢 30%，四倍规模时约慢 48% | 存在稳定可测的差距，仍不足以可靠卡掉比较排序 |
| 庆典计划 | 齿长七的梳形树，在正式上限时约慢 17%，两倍规模时约慢 24%，四倍时约慢 18% | 所测特殊树形和窗口没有形成足够的超时间隔 |
| 粉碎者 | 深链、梳形树和重编号长链上，点分治与线段树仍更快 | 当前测量不支持通过压时限排除这份实现 |
这是对指定程序、输入族与平台的实验结论，不能证明所有合法构造都无法产生更大差距。护林员的排序构造还依赖具体标准库的选主元方式。
正式节点上限分别为 1,000,000、500,000、300,000。两倍、四倍规模只用于性能实验，不属于题目数据范围。出题人解法、Codex 方案及各自地位见三题题解；此处的压力构造由 Codex（GPT-6）提供。
环境、覆盖与测量方法¶
环境见评测环境与性能：Intel Core Ultra 9 275HX、Windows 11、GCC 16.2.0，使用 -std=c++17 -O2 -DNDEBUG -Wall -Wextra -Wpedantic。比较对象为随题 std.cpp 与 alternative.cpp，其源码与二进制哈希均与基础记录核对。
- 单次筛选共 81 份输入：庆典计划与粉碎者各 28 份，护林员 25 份。单次结果只用于选择重复测量对象。
- 原范围内的 10 份候选各重复七次；排序选主元构造在三个规模各重复七次。
- 两道带权树题的四组构造扩大两倍、四倍，共八份输入，各重复五次。
- 两道带权树题另使用随题正式生成器生成重编号长链，各重复七次，纳入时限校准。
重复测量前单独预热并记录峰值工作集，计时交替运行两份程序；同一时刻只运行一份被测程序。计时包含进程启动、读入和输出，排除生成与校验。正文取中位数，完整 JSON保留每次时间、种子、参数和输入/输出哈希。所有程序对在同一输入上的输出哈希一致。原范围内的 11 份重复实验输入均重新生成、核对输入哈希，并通过正式输入校验；两份正式长链另校验输入、输出约束与分组分值。
单次计时确实可能误导。例如护林员的一份山形收益排列，筛选时的耗时比约为 1.59；七次重复后中位数之比为 0.984，没有保留那个差距。因此结论不采用单次筛选中的最大比值。
护林员：把收益顺序变成排序压力¶
任意正整数序列，只要总和为 n-1，都可以作为根所连接的若干条路径的长度。把最长路径放在先，其余路径按顺序分配节点编号，便能让最长链算法按指定顺序收集收益。
生成器的 pivot_guard_gains 针对该版 libstdc++ 的三点取中规则：取当前区间靠前、居中、末尾的元素选主元，降序分区。多数收益为一，少量较大收益被放在连续分区的取样位置。通过模拟交换确定它们最初应在何处，使选中的主元持续接近较大端，每轮只排除很少的元素；剩余的大区间触发 introsort 的深度保护。稀疏的大收益总和只有对数平方级，仍能保持绝大部分收益为一并满足节点总数限制。
| 节点数 | 计数桶 (s) | 比较排序 (s) | 排序 / 桶 | 排序比较次数 |
|---|---|---|---|---|
| 1,000,000 | 0.152050 | 0.196939 | 1.295 | 58,269,639 |
| 2,000,000 | 0.290520 | 0.389631 | 1.341 | 未单独计数 |
| 4,000,000 | 0.578046 | 0.854063 | 1.478 | 257,562,524 |
四百万节点时共 3,996,341 项收益，其中 3,996,256 项为一，最大收益为 89，只有 86 种不同收益。比较次数由独立的插桩程序记录，输出哈希与正式程序一致；插桩耗时不参与比较。
这个构造说明“平均收益很小、重复值很多”并不排除高排序开销。不过两份程序仍共同承担读树、遍历和输出，整份程序的耗时比小于两倍。四百万节点时，仅按该输入的桶计数中位数校准，时限就至少需要向上取整到 1.5 秒，而排序约需 0.854 秒；加入其他输入只可能进一步提高所需时限。
带权树：放大深度、有效查询和分治层数¶
输入族覆盖长链、梳形树、长短臂树、细分二叉树、双扫帚树和递归梳形树。梳形齿长取 1、7、63、1023，细分边长取 16、256、4096；双扫帚的主链约占总点数的二分之一或八分之一。
长度窗口包括完整范围、上界约为节点数的二分之一或三分之一、二次幂附近的上界，以及中间区间。节点数另取二次幂前后。随机、全正、全零与正负交替权值用于改变最优值分布。部分输入固定根后随机重新编号，以改变数组访问顺序。重编号实验与正式计划分别使用 Python random.Random 和 SplitMix64，同一数字种子不表示同一份输入。
庆典计划¶
| 构造 | 节点数 | 单调队列 (s) | 线段树 (s) | 线段树 / 单调队列 |
|---|---|---|---|---|
| 齿长七的梳形树，完整窗口 | 500,000 | 0.369029 | 0.430357 | 1.166 |
| 同族构造 | 1,000,000 | 0.721298 | 0.894051 | 1.240 |
| 同族构造 | 2,000,000 | 1.508678 | 1.785345 | 1.183 |
| 主链占八分之一的双扫帚，完整窗口 | 500,000 | 0.239439 | 0.275956 | 1.153 |
| 同族构造 | 2,000,000 | 0.985321 | 1.093210 | 1.109 |
| 长链，窗口上界约为三分之一 | 500,000 | 0.581406 | 0.608449 | 1.047 |
| 重编号长链，长度 1–249997 | 500,000 | 1.742455 | 1.356307 | 0.778 |
深链配宽窗口的确增加线段树查询循环；但两份程序仍需遍历分治块、收集端点和传播答案，单调队列方案也有多次线性扫描。缩窄窗口又可能增加空查询，未必进一步拉大差距。
重编号长链使单调队列方案更慢，也说明不能只优化“较慢方案最难”的形状而忽略标程在其他合法输入上的表现。编号变化会改变存储访问位置，但没有缓存命中率采样，不能断言全部差异来自缓存。
粉碎者¶
| 构造 | 节点数 | 边分治与单调队列 (s) | 点分治与线段树 (s) | 点分治 / 边分治 |
|---|---|---|---|---|
| 齿长七的梳形树，完整窗口 | 300,000 | 0.518377 | 0.301742 | 0.582 |
| 长链，窗口上界约为三分之一 | 300,000 | 0.665448 | 0.385216 | 0.579 |
| 同族构造 | 600,000 | 1.389752 | 0.781410 | 0.562 |
| 同族构造 | 1,200,000 | 3.018353 | 1.654778 | 0.548 |
| 重编号长链，窗口上界约为二分之一 | 300,000 | 1.085194 | 0.680879 | 0.627 |
| 同族构造 | 600,000 | 2.931970 | 1.787447 | 0.610 |
| 同族构造 | 1,200,000 | 8.143168 | 4.452477 | 0.547 |
在这些输入上，扩树到 2n-1 个节点及边分治的多次线性处理，其实际开销仍超过点分治多出的查询对数。实验未发现能逆转先后顺序、进而形成可靠超时间隔的构造。完整复杂度与操作次数分析见粉碎者题解。
正式范围内的时限校准¶
两道带权树题的正式测试计划均包含 maximum-relabelled-chain，由随题生成器的链与重编号功能生成。与基础测量及正式范围内的重复压力输入合并，取每份程序最慢的用例中位数；规模实验不参与时限计算。
| 题目 | 标程最慢中位数 (s) | 参考时限 (s) | 备用或并列程序最慢中位数 (s) |
|---|---|---|---|
| 护林员 | 0.246618 | 0.5 | 0.254445 |
| 庆典计划 | 1.746265 | 3.5 | 1.393669 |
| 粉碎者 | 1.101980 | 2.5 | 0.680879 |
庆典计划正式重编号长链的单调队列七次计时中位数为 1.746265 秒，线段树为 1.393669 秒；粉碎者分别为 1.101980 和 0.679314 秒。表中各列取整套已测输入上的最大值，可能来自不同输入。目标评测环境仍需重新校准。
复现¶
构造器为 search_adversarial_trees.py，原始结果为 benchmark-tree-stress.json。脚本验证被测源码与二进制和基础记录一致；使用同一编译环境、选项编译六份程序，放到 build/bin/<题目名>[-alternative].exe。
筛选命令：
python tools/search_adversarial_trees.py --stage screen
从保存的结果导出重复实验的参数文件：
import json
from pathlib import Path
report = json.loads(Path("docs/benchmark-tree-stress.json").read_text(encoding="utf-8"))
folder = Path("build/adversarial-trees")
folder.mkdir(parents=True, exist_ok=True)
for name in ("confirm", "pivot", "scale"):
(folder / f"{name}-cases.json").write_text(
json.dumps(report[name]["cases"]), encoding="utf-8")
python tools/search_adversarial_trees.py --stage confirm --cases build/adversarial-trees/confirm-cases.json --repeats 7 --output-name confirm
python tools/search_adversarial_trees.py --stage confirm --cases build/adversarial-trees/pivot-cases.json --repeats 7 --output-name pivot
python tools/search_adversarial_trees.py --stage confirm --cases build/adversarial-trees/scale-cases.json --repeats 5 --output-name scale
正式长链可用各题 tests/generate.py 的 --case maximum-relabelled-chain 生成。calibrate_tree_stress.py 从已保存的 JSON 读取参数，调用 profile_priority_work.py 的 instrument 函数重建排序计数程序，生成输入并校验哈希；计数程序不用于计时。
python tools/calibrate_tree_stress.py --cxx g++ --verify-only
省略 --verify-only 时，还会生成、校验并重新测量两道带权树题的正式长链，结果写入 build/adversarial-trees/calibration.json。--cxx 可指定编译器完整路径；应使用测量记录中的编译环境。此过程不依赖手工保存的计数文件，也不改写公开的历史测量结果。
生成器哈希记录各次运行所用的版本。校验记录中的 matches_measured_input 表示构造器重建的输入与对应实测输入完全一致。
English summary¶
Targeted constructions produce a measurable gap for Forest Ranger: median-of-three pivot inputs make sorting about 30% slower at the formal limit and 48% slower at four times that size. Festival Plan's comb inputs give roughly 17–24% differences; Grinder's centroid-and-segment-tree implementation remains faster on the measured inputs. None supplies a reliable exclusion gap while reserving twice the reference time and rounding up to 0.5 seconds. This finite experiment does not prove that no other construction can do so.
The tables report repeated medians. The 81 single-run screening cases are used only to select candidates. Formal-limit confirmations and pivot inputs use seven runs; scaled weighted-tree inputs use five. Randomly relabeled chains are included in both weighted-tree formal plans. Reference medians across measured legal inputs give limits of 3.5 seconds for Festival Plan and 2.5 seconds for Grinder. Larger experimental sizes do not change the published constraints. Full timings, hashes, seeds and validation records are in the linked JSON; construction credit goes to Codex (GPT-6).