CF 2005B2 The Strict Teacher (Hard Version) 是 Codeforces Round 2005 Div.2 的 B2 题。这题我在 Virtual Contest 里第一次交就 WA 了一发WA 得特别冤——不是思路没想通而是边界上的老师到底算不算能站的位置没理清楚。先把题意说清楚数轴上有 n 个房间m 个老师占着其中 m 个不同的房间老师在房间里不动。David 想找一个房间躲离所有老师越远越好。Easy 版本每次给一个位置 x问 David 站在 x 时离最近老师有多远排序加两次二分就能回答Hard 版本每次给一个区间 [l, r]David 可以在区间里任意选房间问题是这个区间里能选到的最大最近老师距离是多少。这题适合正在练二分查找、掌握 RMQ 但不熟怎么和二分结合的人也适合想弄懂最值问题如何转化为候选点集合的选手。下面我把从题意到公式再到实现的完整链路拆开讲。1. 从Easy到Hard题目到底在问什么1.1 Easy版本单点查询就是最近邻居距离先花两句话把 Easy 版本讲完因为 Hard 版本的所有边界处理都建立在它的基础上。给出查询位置 x 之后问题变成求 min |x - t_i|t_i 是老师位置。把老师位置排序用lower_bound找到第一个大于等于 x 的老师它就是右侧最近候选迭代器向前挪一位就是左侧最近候选。两个距离取小得到答案。这里大部分人都不会写错但有一个细节很多人第一次写会漏如果lower_bound返回的迭代器正好指向 x 本身说明 x 就是老师位置右侧距离是 0答案直接是 0。处理这个情况只需要把两个方向的候选都算出来再取 min不需要特判。1.2 Hard版本从一个点变成一个区间B2 把查询从点 x 扩张成区间 [l, r]。David 可以选择区间中任意整数房间每个房间 x 有一个安全距离 f(x)到最近老师的距离问题是求 f(x) 在 [l, r] 上的最大值。我第一次看到这个改动第一反应是那就在区间里三分——但 f(x) 根本不是单峰函数它是一堆倒 V 拼起来的锯齿全局三分必挂。这也是这题和普通二分题最大的区别我们要最大化的不是某个单调函数而是一个分段线性函数。1.3 直接枚举为什么不行如果每次查询暴力检查区间里每个点最坏是 O(nq)n 和 q 都到 2e5 级别直接爆炸。就算只检查老师位置和相邻老师的中点也不够因为区间可能很短、不包含任何中点最优解落在端点附近区间也可能很长横跨好几个老师对需要考虑这些相邻老师对里哪个 gap 最大。所以问题的本质是把连续空间上的最优化离散化找到有限个关键位置然后用数据结构处理区间查询。下面这节就推导这些关键位置到底是什么。2. 破题关键安全距离函数是倒V折线2.1 把问题建模成 f(x)定义 f(x) min_i |x - t_i|也就是位置 x 到最近老师的距离。我们要的是 max_{x in [l, r]} f(x)。把老师位置排序后整个数轴被 m 个老师分成 m1 段。最左边和最右边的段是单侧有老师的段在第一个老师左边f(x) 随着 x 增大而减小越靠近老师越危险在最后一个老师右边f(x) 随着 x 增大而增大。这两段里f 在查询区间上的最大值一定出现在区间端点——因为它是单调的。中间 m-1 个段更有意思。每个段夹在相邻老师 t_i 和 t_{i1} 之间段内 f(x) min(x - t_i, t_{i1} - x)。这是一个标准的倒 V 形左半边 x - t_i 更小所以 f(x) x - t_i随 x 增大而增大右半边 t_{i1} - x 更小所以 f(x) t_{i1} - x随 x 增大而减小。最大值出现在顶点也就是两个老师的中点值是 (t_{i1} - t_i) / 2。2.2 最大值只出现在两类位置对任意查询区间 [l, r]f(x) 在这个区间内的最大值只可能出现在三种地方区间左端点 l区间右端点 r某个倒 V 的顶点前提是这个顶点落在 [l, r] 内部。为什么因为 f 在每一段里都是分段线性的每一段上的最大值不是在段端点就是在倒 V 顶点。段端点要么是老师位置f 0不可能是最大值要么恰好是 l 或 r。所以把三类候选全部算出来取 max就是答案。这个结论是整个题的核心后面所有代码都围绕它展开。我最初没有严格证明就直接写结果在中点不在区间内时边界候选能不能兜底这个问题上栽了跟头后面专门讲。2.3 三类候选答案的定义把上面的结论翻译成可操作的候选集合候选 1f(l)即 David 站在区间左端点时的安全距离候选 2f(r)右端点同理候选 3所有满足中点落在 [l, r] 内的相邻老师对取它们的中点安全距离最大值。候选 3 需要再解释一下。每个相邻老师对 (t_i, t_{i1}) 能提供的峰值安全距离是 best_i (t_{i1} - t_i) / 2整数除法向下取整。这个峰值在物理上对应两个老师正中间的几个房间。如果查询区间把这些房间包进去了David 就能拿到这个峰值如果没包进去就老老实实看边界候选。3. 边界候选的二分细节lower_bound与upper_bound要配对用3.1 f(l) 的求法lower_bound 找右侧第一个 l 的老师求 f(l) min(左侧最近老师距离, 右侧最近老师距离)用一个lower_bound就能同时拿到两侧信息auto it lower_bound(t.begin(), t.end(), l); int fl INT_MAX; if (it ! t.end()) fl min(fl, *it - l); // 右侧有老师 if (it ! t.begin()) fl min(fl, l - *(it - 1)); // 左侧有老师这里用lower_bound是因为 l 本身可能是老师位置。如果 l 是老师位置lower_bound会返回指向 l 自己的迭代器右侧距离是 0fl 被更新为 0语义正确——l 这个位置被老师占了David 站不了安全距离就是 0。这个 0 不会污染答案因为答案是取 max。3.2 f(r) 的求法为什么必须用 upper_bound求 f(r) 时很多第一次写的人会照抄lower_bound这是最容易犯错的地方。右侧最近老师必须是严格大于 r的老师而不是大于等于 r。如果 r 恰好是老师位置lower_bound会返回 r 自己这会把r 本身是老师误当成r 右边还有一个老师虽然算出来的左距离 r - *(it-1) 也是 0 不影响答案但语义就乱了。正确写法是用upper_boundauto it2 upper_bound(t.begin(), t.end(), r); int fr INT_MAX; if (it2 ! t.end()) fr min(fr, *it2 - r); // 右侧有老师严格大于 r if (it2 ! t.begin()) fr min(fr, r - *(it2 - 1)); // 左侧有老师小于等于 rit2 - 1指向最后一个小于等于 r 的老师如果它刚好等于 r说明 r 位置被老师占了左距离 0fr 0没问题。我个人的经验是求左端点用 lower_bound求右端点用 upper_bound成对记。这个口诀能帮你少交两次 WA。3.3 手算验证两个查询对比拿老师位置 [10, 20, 30] 来手算两组查询确保边界候选和内部候选的关系是清楚的。查询 [12, 18]f(12)左老师 10 距离 2右老师 20 距离 8f(12) 2f(18)左老师 20 距离 2右老师 30 距离 12最近是 2内部候选相邻对 (10,20) 的中点是 15best 5(20,30) 的中点是 25best 5。只有 15 落在 [12, 18] 内候选 5答案 max(2, 2, 5) 5。David 选房间 15离 10 和 20 都是 5。查询 [12, 14]f(12) 2f(14)左老师 10 距离 4右老师 20 距离 6f(14) 4内部候选(10,20) 的中点是 15(20,30) 的中点是 25都不在 [12, 14] 内没有候选答案 max(2, 4) 4。David 选房间 14离 10 是 4离 20 是 6安全距离 4。第二个例子是关键15 虽然是最优位置但它不在查询区间里David 够不到所以内部候选不能算。这验证了内部候选的中点必须落在 [l, r] 内这个条件不是可选项而是必须的。4. 内部候选的批量处理中点数组 稀疏表4.1 把相邻老师对压缩成候选点如果每次查询都遍历所有相邻老师对复杂度是 O(mq)肯定过不了。但观察候选 3 的定义每个相邻老师对贡献一个峰值安全距离 best_i只有当它的中点落在查询区间内时才有效。于是可以把每个相邻老师对压缩成一个点点的位置pos_i中点代表位置点的权值val_i best_i。问题就变成静态数组中查询 [l, r] 区间内的最大值。这是一个标准的 RMQ区间最值查询可以用稀疏表 O(1) 回答。4.2 中点代表位置的选取与奇偶 Gap有一个细节必须处理两个老师之间的距离 gap 可能是奇数。比如老师在 10 和 19gap 9best 9 / 2 4。真正达到安全距离 4 的房间有两个14 和 1514 离 10 是 4离 19 是 515 离 10 是 5离 19 是 4。我取 pos t_i best_i 10 4 14只代表其中一个。那如果查询区间恰好是 [15, 15]pos 14 不在区间内内部候选是不是就漏了不会。因为 f(15) min(15 - 10, 19 - 15) min(5, 4) 4边界候选 f(r) 会把 4 带出来。也就是说中点取整丢掉的那个位置如果确实在查询区间内它到某侧老师的距离恰好等于边界候选能算出来的值。这就是 2.2 节说的边界候选兜底在实际中的体现。4.3 稀疏表 vs 线段树静态数组区间最值的首选这里我用稀疏表而不是线段树原因很简单数组是静态的没有修改操作稀疏表预处理 O(m log m)、单次查询 O(1)代码也短。线段树虽然支持修改但单次查询 O(log m)常数大代码长在这道题属于杀鸡用牛刀。方案预处理单次查询支持修改代码量稀疏表O(m log m)O(1)否短线段树O(m)O(log m)是较长分块O(m)O(sqrt(m))可扩展中等4.4 RMQ 代码片段稀疏表的构建和查询写法如下这里st[j][i]表示从 i 开始长度为 2^j 的区间最大值int pairs m - 1; vectorint pos(pairs), val(pairs); for (int i 0; i pairs; i) { val[i] (t[i 1] - t[i]) / 2; pos[i] t[i] val[i]; } int K 1; while ((1 K) pairs) K; vectorvectorint st(K, vectorint(pairs)); for (int i 0; i pairs; i) st[0][i] val[i]; for (int j 1; j K; j) { int half 1 (j - 1); int len 1 j; for (int i 0; i len pairs; i) { st[j][i] max(st[j - 1][i], st[j - 1][i half]); } } auto rmq [](int l, int r) { int len r - l 1; int j 31 - __builtin_clz(len); return max(st[j][l], st[j][r - (1 j) 1]); };这里的__builtin_clz是 GCC 内置的计算前导零个数函数31 - __builtin_clz(len)就是 log2(len) 向下取整。如果不喜欢用内置函数可以用__lg(len)效果一样。5. 完整可提交代码与复杂度验证5.1 完整 C 代码把前面所有部分拼起来完整代码长这样#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n, m, q; cin n m q; vectorint t(m); for (int i 0; i m; i) cin t[i]; sort(t.begin(), t.end()); int pairs m - 1; vectorint pos, val; if (pairs 0) { pos.resize(pairs); val.resize(pairs); for (int i 0; i pairs; i) { val[i] (t[i 1] - t[i]) / 2; pos[i] t[i] val[i]; } int K 1; while ((1 K) pairs) K; vectorvectorint st(K, vectorint(pairs)); for (int i 0; i pairs; i) st[0][i] val[i]; for (int j 1; j K; j) { int half 1 (j - 1); int len 1 j; for (int i 0; i len pairs; i) { st[j][i] max(st[j - 1][i], st[j - 1][i half]); } } auto rmq [](int l, int r) { int len r - l 1; int j 31 - __builtin_clz(len); return max(st[j][l], st[j][r - (1 j) 1]); }; while (q--) { int l, r; cin l r; int ans 0; auto it lower_bound(t.begin(), t.end(), l); int fl INT_MAX; if (it ! t.end()) fl min(fl, *it - l); if (it ! t.begin()) fl min(fl, l - *(it - 1)); ans max(ans, fl); auto it2 upper_bound(t.begin(), t.end(), r); int fr INT_MAX; if (it2 ! t.end()) fr min(fr, *it2 - r); if (it2 ! t.begin()) fr min(fr, r - *(it2 - 1)); ans max(ans, fr); int pl lower_bound(pos.begin(), pos.end(), l) - pos.begin(); int pr upper_bound(pos.begin(), pos.end(), r) - pos.begin() - 1; if (pl pr) ans max(ans, rmq(pl, pr)); cout ans \n; } } else { while (q--) { int l, r; cin l r; int ans 0; auto it lower_bound(t.begin(), t.end(), l); int fl INT_MAX; if (it ! t.end()) fl min(fl, *it - l); if (it ! t.begin()) fl min(fl, l - *(it - 1)); ans max(ans, fl); auto it2 upper_bound(t.begin(), t.end(), r); int fr INT_MAX; if (it2 ! t.end()) fr min(fr, *it2 - r); if (it2 ! t.begin()) fr min(fr, r - *(it2 - 1)); ans max(ans, fr); cout ans \n; } } } return 0; }5.2 复杂度与数据规模验证排序O(m log m)稀疏表预处理O(m log m)每组查询两次 lower_bound/upper_bound 是 O(log m)RMQ 是 O(1)总体 O(log m)。总复杂度 O((m q) log m)在 m 和 q 都是 2e5 级别时可以稳稳通过。空间上稀疏表是 O(m log m)大约 2e5 * 18 个 int完全没问题。关于 pos 数组能不能二分需要确认它是严格递增的。相邻两个 pos 的差 pos_{i1} - pos_i (t_{i1} - t_i) - (t_{i1} - t_i)/2 (t_{i2} - t_{i1})/2 这个值必然大于等于 1所以 pos 严格递增lower_bound和upper_bound可以直接用。6. 提交过程中的踩坑记录与扩展思考6.1 坑一奇偶 Gap 的代表位置不是唯一最优位置我最初把 pos 写成 (t[i] t[i1]) / 2也就是数学意义上的中点向下取整。对于奇数 gap比如老师在 1 和 100gap 99best 49pos (1 100) / 2 50。这是对的因为 50 离 1 是 49、离 100 是 50安全距离 49房间 51 离 1 是 50、离 100 是 49安全距离也是 49。但如果你以为只有 pos 这一个房间能达到最优就大错特错了奇偶 gap 会给两个最优房间。这带来一个隐患如果你在内部候选里用的是区间内所有 pos 的最大 val那对于查询 [51, 51]pos 50 不在区间内部候选算不出来但实际答案应该是 49站在 51 离 100 是 49。这时候只有靠边界候选 f(l) f(51) min(51-1, 100-51) min(50, 49) 49 来兜住。边界候选和内部候选必须互相兜底缺一个都不完备。6.2 坑二边界候选与内部候选必须互相兜底上面例子引出一个很重要的调试思路你可以构造一些对称数据来验证两类候选是否都正常工作。比如老师在 [5, 15]查询 [5, 15]f(5) 05 是老师位置f(15) 015 是老师位置内部候选(5,15) 的中点 pos 10val 5落在区间内候选 5答案 5。David 选 10离 5 和 15 都是 5。如果我把内部候选的区间定位写错比如用了 lower_bound 而不是 upper_bound 找 pr这个例子很可能输出 0。所以我在本地测试时专门写了这种查询区间两个端点都是老师的数据用来验证内部候选有没有生效。6.3 坑三为什么不建议写二分答案 空隙检查这题其实还有一种思路二分答案 D判断 [l, r] 内是否存在一个位置 x使得所有老师到 x 的距离都 D。等价于判断每个老师的安全半径 [t_i - D 1, t_i D - 1] 的并集是否完全盖住 [l, r]如果有空隙就存在这样的 x。理论上这个做法也能过但每个查询要二分 D大约 30 次每次判断还要二分老师位置log m整体复杂度 O(q log n log m)而且代码里要处理区间合并的边界比中点 RMQ 的思路绕得多。我更推荐把中点 RMQ 当成这类题的标准答案因为它把问题结构看得更清楚。6.4 这套候选点 区间最值思想的推广把每对相邻障碍物的中点看成一个候选点用区间最值查询处理落在查询区间内的候选这个套路在一维数轴上非常通用。比如最大化到最近禁止位置的距离在给定区间内放置物品使得离所有限制点最远这类问题基本都可以套这个思路先找关键位置再用数据结构回答区间查询。这个思想也可以延伸到二维的曼哈顿距离问题只是候选点会变成四个方向的极值处理起来更复杂。但核心逻辑不变连续空间的最优化先离散化到有限候选集再上数据结构。最后分享一个我自己的调试技巧这类题 WA 之后不要直接看题解先构造小数据手算然后把代码里的每个候选值都cerr打印出来和手算结果对一遍。边界候选两个值、内部候选一个值三个值一对基本能立刻定位是二分用错了还是 RMQ 区间查错了。这比对着大数据发呆高效得多。