输出敏感分析

许多输入对象不会成为答案，却必须被读取或用于排除。分析时给这两类工作分别记账：定位、搜索或预处理支付“找到答案”的成本；每报告一项，再支付与这一项有关的成本。关键不是在公式末尾添一个 $k$，而是证明所有扫描都能记在少量定位步骤或真实输出上。

这也解释了为什么“小答案”有时仍不便宜。即使凸包只有三个极点，算法通常仍须查看所有输入点，确认没有遗漏一个外部点；输出敏感性会减少超过这份输入检查的额外工作，而不会自动免除读取输入。

区间查询中，停止比较记给谁 ​

在中心区间树公理库区间树Interval tree · Centered interval tree按中心点递归存放跨中心区间，并以两套端点次序支持动态区间集合上的 stabbing 与交叠报告查询。的一个节点，中心为 $10$，驻留的闭区间按左端点排序为

查询 $q=8<10$ 时，所有驻留区间的右端点已经满足 $high\ge 10>8$。只需扫描左端点：

最后一项未被输出，但并非没有成本。每个访问节点至多有一次这样的停止比较，其余被读项都各自对应一个输出。随后只进入左子树，右子树的区间全在中心右侧，不可能含 $8$。若树高为 $H$，整条搜索路径的非输出工作为 $O(H)$；每个区间只驻留一处，输出工作为 $O(k)$，合计 $O(H+k)$。只有中心骨架确实保持 $H=O(\log n)$ 时，才能代入得到 $O(\log n+k)$。

静态构造可用平衡的中心选择保证树高；动态版本还需说明固定坐标宇宙或重建策略。端点表支持有序顺次遍历也是该计费的实现条件：若每取下一项都重新从树根搜索，便平白加入了逐项对数因子。

不知道凸包大小时怎样猜 ​

考虑 $n\ge 3$ 个互异平面点，先假定无三点共线，输出凸包公理库凸包Convex hull包含给定点集的最小凸集，是凸几何中的基本包络对象，并可进一步研究其算法构造。的 $h$ 个极点。Chan 的分组路线把 Jarvis wrapping 的“一步扫描全部点”换成“一步询问各组凸包”。给定步数预算 $H$ 和组大小 $m$，执行以下过程：

1. 分成 $\lceil n/m\rceil$ 组，各组至多 $m$ 点；分别计算只保留极点的局部凸包并按环序存储，总计 $O(n\log m)$。
2. 从全局极点出发；每一步在各局部凸包上求支持切线，以二分切线查询取得该组的候选，再从这些候选中选出下一个全局极点。若允许共线点，组内切线选择和组间候选比较都在从当前顶点出发方向相同的候选中选择距离最远者，跳过同一条边上的非极点。每步成本为 $O((n/m)\log m)$。
3. 回到起点即输出整个环；执行 $H$ 步仍未闭合则返回 incomplete，不能把这段前缀当作最终凸包。

每一步选的是支持整组、进而支持全部输入的下一条边，因此已生成的前缀始终是全局边界的一段。取 $m=H\le n$，成功或失败的一轮都至多耗费 $O(n\log H)$。切线查询依赖凸多边形的环序和精确方向测试公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。；这里把它作为几何子程序，不把任意数组二分搜索当作它的替代。

未知 $h$ 时依次取

设首次成功在第 $T$ 轮。若不是首轮，上一轮失败保证 $2^{2^{T-1}}<h$；所以 $2^T<2{\log }_{2}h$。每轮重新建局部凸包也无妨，因为

例如 $h=20$ 时，预算为 $4,16,256$（受 $n$ 截断），相应对数成本刻度是 $2,4,8$，总和仍与最后一项同阶。若每轮不复用预处理，却只把预算依次翻倍为 $2,4,8,\dots$，得到的账本是 $n(1+2+\cdots +\lceil {\log }_{2}h\rceil )$，只证明 $O(n(\log h{)}^2)$；普通翻倍并不能直接替代上述双指数猜测。

上述最远点规则也处理只有部分点共线的情形。例如从 $(0,0)$ 沿同一方向遇到 $(1,0)$ 和 $(2,0)$ 时，应直接选择 $(2,0)$，否则会把边上的中间点误计入极点数 $h$。空集、单点和全共线情形单独处理；若只报极点，全共线输入输出至多两个端点。若要求全部共线边界输入点，输出参数就变了。把这些情形一起写入，可用 $O(n\log max\{2,h\})$ 避免 $h\le 1$ 时的对数歧义。

Aho–Corasick 自动机公理库Aho–Corasick 自动机Aho–Corasick automaton · AC automaton把模式 Trie 与失败链接结合成一次扫描识别多个模式的确定有限自动机。的输出链把每个报告步骤记给一个匹配，因而扫描是 $O(n+z)$；若只需每个模式的出现次数，可以累计状态访问数再沿失败树汇总，未必需要逐个生成全部 $z$ 个位置。这正是报告接口与计数接口的差别。

扫描线公理库扫描线范式Sweep-line paradigm · Plane sweep按事件推进一条虚拟直线，并用动态有序状态维护当前横截面组合关系的计算几何范式。报告 $K$ 个交点时，事件处理还可能逐项需要树更新，故出现 $O((n+K)\log n)$；输出敏感不保证每个结果只付常数。阅读一个新保证时，可以依次检查“输出是什么、什么工作能记给输出、还有多少未输出工作”。用上面的例子自测：指出 $q=8$ 的第三次比较由树高项支付，再分别求出双指数猜测与普通翻倍的成本和；两个证明回答的是不同的额外开销。