鱼变区间、渔民变查询点：Fishermen 排序二分与区间覆盖全解

今天打卡到第2946题正好是 P5867 [SEERC 2018] Fishermen。这题我此前在好几个信奥交流群里见人提过一直没认真做这次趁着刷题进度排到它完整推了一遍。题目本身不复杂但思维转化的过程非常典型很适合用来练“几何问题转区间问题”这一套路。整道题的核心就一句话把一条鱼能被哪些渔民钓到看成一个区间然后离线排序、二分计数。就这么个思路能把 O(NM) 的暴力降到 O((NM) log(NM))在 N、M 都到 1e5 的数据范围下稳稳跑完。下面把题面拆解、推导过程和完整 C 实现一次性写透顺带把我踩过的几个坑也交代清楚。1. 题目解读Fishermen 到底在问什么1.1 场景模型与输入输出结构这道题源自 SEERC 2018东南欧区域赛题面背景很生活化一个湖里分布着 N 条鱼湖边站着 M 个渔民每个渔民手里有一根长度为 L 的鱼竿。鱼在湖里有自己的坐标渔民站在岸上位置已知。问每个渔民最多能钓到多少条鱼。判断标准很简单鱼和渔民之间的直线距离不超过 L就算能被钓到。放到坐标系里看这个模型的几何约束其实非常清晰。鱼的位置用 (x_i, y_i) 表示渔民的位置全部落在一条直线上。我按常见的题目设定来理解这条直线是 y 0也就是把湖岸视为 x 轴渔民在 (X_j, 0) 的位置鱼在 x 轴上方的水域里。那么对于第 i 条鱼和第 j 个渔民能被钓到的条件就是勾股定理(x_i - X_j)² y_i² ≤ L²隐藏条件是鱼竿长度有限所以如果 y_i L这条鱼无论水平距离多近都不可能被钓到代码里直接跳过即可。输入格式通常是第一行给出 N、M、L然后 N 行鱼坐标之后 M 行渔民的 x 坐标。输出要求按渔民给出的顺序逐个输出每个渔民能钓到的鱼的数量。1.2 核心转化鱼变成区间渔民变成查询点这道题最关键的思维节点不是怎么算距离而是怎么把“鱼”这个概念从点变成区间。我们把上面那个不等式单独对 X_j 做变形。先把含 X_j 的项放到一边(x_i - X_j)² ≤ L² - y_i²这个式子成立的前提是 L² - y_i² ≥ 0也就是 y_i ≤ L否则右边是负数左边平方项永远非负不等式不可能成立。在 y_i ≤ L 的前提下两边开方得到|x_i - X_j| ≤ sqrt(L² - y_i²)也就是说渔民要想钓到这条鱼他的横坐标 X_j 必须落在区间 [x_i - w, x_i w] 内其中 w floor(sqrt(L² - y_i²))。这里取 floor 是因为坐标全是整数我们只需要整数范围内有没有解。经过这一步原题就彻底变了N 条鱼等价于 N 个区间 [l_i, r_i]M 个渔民等价于 M 个查询点 X_j。问题变成“每个点被多少个区间覆盖”。这种转化在计算几何里非常常见本质上是把二维距离约束投影到一维坐标轴上。一旦想到这一步后面的代码其实就没什么算法难度了剩下的全是排序和二分这种基本功。所以这道题表面是几何题实际考的是“能不能把几何关系抽象成区间模型”这也是信奥题里很爱设的一道坎。2. 解法设计为什么排序与二分能解决问题2.1 暴力做法的复杂度瓶颈先看如果想不到区间转化直接硬做会是什么后果。对每条鱼遍历所有渔民计算距离判断是否在 L 内代码五分钟能写完但复杂度是 O(NM)。当 N 和 M 都是 1e5 级别时总操作次数是 1e10这在任何 OJ 上都跑不动。即便 N、M 都只有 1e41e8 的运算量也已经很勉强了。所以必须把复杂度降下来。区间转化之后问题就变成了一个非常经典的“离线查询”模型。为什么叫离线因为我们可以先把所有鱼的区间准备好再把所有渔民的坐标准备好统一排序处理而不是每来一个渔民都重新扫一遍所有鱼。这种把所有查询收集起来一次性处理的思路在信奥里叫离线化处理是处理大批量查询问题的基本盘。顺着这个思路核心目标就变成快速回答 M 个查询点每个点被多少个区间覆盖。这里有个非常漂亮的性质——覆盖次数不需要维护什么高级数据结构只要分别统计“左端点不超过查询点的区间数”和“右端点小于查询点的区间数”两者相减就是答案。下面详细说这个公式是怎么来的。2.2 区间覆盖计数公式推导考虑一个点 x 和一个区间 [l, r]。这个区间覆盖点 x当且仅当 l ≤ x 且 r ≥ x。如果我把“l ≤ x”的区间全部数出来会多算一类那些 l ≤ x 但 r x 的区间因为它们的右端点已经落在 x 左边了实际上并没有覆盖住 x。所以覆盖 x 的区间数 (满足 l ≤ x 的区间数) - (满足 r x 的区间数)这个公式里有一个特别容易写错的细节第二个条件是 r x而不是 r ≤ x。因为当 r x 时区间 [l, x] 的右端点正好压在查询点上闭区间是包含端点的这个区间应该算作覆盖了 x。如果用 r ≤ x 去数就会把一个正好贴边的区间误减掉导致答案少 1。为了验证这个公式我手算了一组小数据。设三条鱼的区间分别为 [0, 2]、[1, 5]、[0, 0]查询点取 x 1。从图上直接看覆盖 x 1 的区间是前两个答案是 2。用公式算l ≤ 1 的区间有三个三个区间的左端点都 ≤ 1r 1 的区间只有一个[0, 0] 的右端点 0 13 减 1 等于 2和直接数是一致的。有了这个公式问题就只剩下“如何高效统计数量”。把 N 个左端点放进一个数组排序把 N 个右端点放进另一个数组排序。对于查询点 x用二分查找分别在两个数组里定位l ≤ x 的数量 upper_bound(左端点数组, x) 的下标r x 的数量 lower_bound(右端点数组, x) 的下标两次二分都是 O(log N)M 个查询总复杂度 O(N log N M log N)排序占 O(N log N)整体就是 O((NM) log N)完全够用。2.3 优先队列扫描的替代做法除了排序二分这道题还有一个等价做法就是按坐标从左到右扫描配合优先队列维护当前活跃的区间。思路是这样的把鱼区间按左端点从小到大排序渔民坐标也排序。扫描过程维护一个小根堆堆里存的是已经入场但还没退场的区间右端点。处理到一个渔民坐标 x 时先把所有 l ≤ x 的区间右端点加入堆然后把所有 r x 的堆顶元素弹出此时堆的大小就是覆盖这个点的区间数。这种做法和排序二分本质上是一回事区别在于二分法分别独立统计左右端点扫描法则通过堆把“入场”和“退场”统一在一个数据结构里处理。在实际做题中二分法代码量更短逻辑更好验证所以我推荐首选二分法。扫描法适合在你想加深理解的时候写一遍写完能明显感觉到两类数据结构在解决同一问题时的不同节奏。3. 完整 C 实现与核心细节3.1 变量类型与读入处理写 C 代码时第一件事就是确认数据范围。这题坐标和 L 的取值范围都是 1e9 级别所以 x、y、L、区间端点、渔民坐标一律用 long long 存。用 int 会在计算 L² - y² 的时候直接溢出WA 得莫名其妙。既然涉及距离平方中间值最大是 1e18long long 的上下限大约是 ±9.22e18能装得下但要记住这个上限后面写平方根微调时也要注意乘法别超界。读入方面我习惯在 main 函数开头加两行ios::sync_with_stdio(false); cin.tie(nullptr);信奥题输入量大时这两行能明显减少 cin 的耗时。对于本题不加也能过但养成本能性地加上总没错。尤其是有时候 OJ 环境比较苛刻C 的 iostream 默认同步 C 标准 IO 的开销不是小事。3.2 生成区间时的 sqrt 精度坑这里是我认为全题最容易翻车的地方。我们要算 w floor(sqrt(L² - y²))其中括号里面的值是一个精确的 long long 整数。很多人直接写long long w sqrt(L * L - y * y);然后顺利 WA。问题出在哪C 的 sqrt 接收 double 参数返回 double。当 L² - y² 是一个完全平方数比如恰好等于 1e18 这种量级的数时double 的有效精度大约只有 15 到 16 位十进制数字根本存不下 1e18 级别的精确整数值。于是 sqrt 的结果可能算出 999999999.99999994 之类的东西转成 long long 后强制截断成 999999999比正确答案少 1。一组数据出这种偏差答案就错一个而且极难肉眼发现。我一开始就踩了这个坑后来查题解看到有人直接二分求整数平方根才反应过来这种题目就应该尽量避免浮点运算。简单可靠的修法有两个。方法一先求得近似值再微调修正long long d L * L - y * y; long long w sqrt((long double)d); while ((w 1) * (w 1) d) w; while (w * w d) --w;这个思路是利用平方数之间的间隔远大于浮点误差通过两次 while 循环把偏差拨正。注意 (w 1) * (w 1) 可能接近 1e18 量级long long 能承受但要保证 d 不超过 1e18否则乘法溢出。本题 L 上限 1e9所以安全。方法二直接用整数二分求平方根完全不碰浮点long long sqrtll(long long v) { long long l 0, r 1e9 1; while (l r) { long long mid (l r 1) 1; if (mid * mid v) l mid; else r mid - 1; } return l; }当 v 最大为 1e18 时二分范围可以放宽到 1e9 1mid * mid 最大约 1e18不会溢出。两种方式我都测试过都能稳定通过。我个人推荐第二种因为整型二分的行为完全确定不会出现浮点环境差异导致的提交结果不稳定。代码里我两种都提供实际做题时可以按自己的习惯挑一种。3.3 区间统计部分的二分细节区间生成并存入两个 vector一个存左端点一个存右端点排序之后就到了统计环节。这里有两个二分函数的分工要理清upper_bound(first, last, x)返回第一个大于 x 的迭代器。用它数“l ≤ x 的数量”因为结果下标恰好是满足条件的元素个数。lower_bound(first, last, x)返回第一个大于等于 x 的迭代器。用它数“r x 的数量”因为返回下标之前的所有元素都严格小于 x。这两个选错任何一个答案都会错。我见过不少人混淆 upper_bound 和 lower_bound 的语义用反了还查不出问题。可以在代码里加注释提醒自己左端点用 upper_bound取等右端点用 lower_bound不取等。背后的原因前面已经推导过了闭区间导致右端点相等时不能减。两个数组排序完后统计部分的核心代码只有三行int leftCnt upper_bound(Ls.begin(), Ls.end(), x) - Ls.begin(); int rightCnt lower_bound(Rs.begin(), Rs.end(), x) - Rs.begin(); int ans leftCnt - rightCnt;3.4 完整代码与注释我把完整实现贴在下面注释写得比较详细方便直接对照理解。#include bits/stdc.h using namespace std; struct FishInterval { long long l, r; }; long long sqrtll(long long v) { long long l 0, r 1000000001LL; // 坐标上限 1e9平方根不可能超过它 while (l r) { long long mid (l r 1) 1; if (mid * mid v) l mid; else r mid - 1; } return l; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; long long L; cin N M L; vectorFishInterval fishes; for (int i 0; i N; i) { long long x, y; cin x y; if (y L) continue; // 垂直距离已经超过竿长不可能钓到 long long d L * L - y * y; long long w sqrtll(d); // 区间 [x - w, x w] 内的渔民都能钓到这条鱼 fishes.push_back({x - w, x w}); } vectorlong long xs(M); for (int i 0; i M; i) { cin xs[i]; } vectorlong long Ls, Rs; Ls.reserve(fishes.size()); Rs.reserve(fishes.size()); for (auto f : fishes) { Ls.push_back(f.l); Rs.push_back(f.r); } sort(Ls.begin(), Ls.end()); sort(Rs.begin(), Rs.end()); for (int i 0; i M; i) { long long x xs[i]; // 覆盖 x 的区间数 l x 的区间数 - r x 的区间数 int leftCnt upper_bound(Ls.begin(), Ls.end(), x) - Ls.begin(); int rightCnt lower_bound(Rs.begin(), Rs.end(), x) - Rs.begin(); cout leftCnt - rightCnt \n; } return 0; }代码结构很直白读鱼生成区间读渔民排序左右端点逐个查询输出。整个程序去掉空行大概 60 行时间复杂度 O((NM) log N)空间复杂度 O(N)。4. 常见问题与调试心得4.1 边界数据鱼刚好在竿长边界很多人做题时不会故意构造边界数据导致一些隐藏问题在本地样例上根本暴露不出来。拿这道题来说边界情况有两种值得专门测。第一种是 y 恰好等于 L此时 d 0w 0区间变成单点 [x, x]。比如鱼在 (0, 2)渔民在 (0, 0)竿长 2这条鱼应该能被钓到。用公式统计时区间 [0, 0] 的左端点 0 ≤ 0右端点 0 0 为假所以不会被减去答案正确。如果统计右端点时错用成 upper_bound即 r ≤ x这个单点就恰好被减掉了漏算一条鱼。第二种边界是查询点 x 正好落在区间右端点上比如区间 [1, 3]查询点 3。这个点应该被覆盖因为闭区间包含右端点。用 lower_bound 数右端点时3 不会被算进“r x”所以保留了这个区间答案正确。这类边界问题最好自己在草稿上演算一遍确保两个二分的处理逻辑无懈可击而不是靠碰运气。4.2 坐标范围与负数坐标的处理区间端点可能算出来是负数例如鱼在 x -5w 3左端点是 -8。这没有任何问题排序时负数默认在最前面upper_bound 和 lower_bound 处理的是迭代器区间不关心元素本身是否非负。不需要做偏移或离散化用 long long 原样保持即可。有一点需要提醒如果你做的是“把坐标轴偏移到非负再差分”那类做法就要小心处理负数坐标和偏移量。但本题用的是排序二分天然不受负数影响这点也是我偏爱这个做法的原因之一逻辑上少一层转换就少一个出错点。4.3 多次提交最常见的错误把容易踩的坑集中整理成一张速查表方便提交前逐一自检问题现象常见原因处理方式大面积答案偏大忘记跳过 y L 的鱼读入后先判断 y L 则 continue个别答案比正确小 1sqrt 浮点精度损失用整数二分或 while 微调求平方根数组越界或编译报错变量类型用了 int坐标类变量一律 long long答案整体错乱二分的 upper_bound 和 lower_bound 用反左端点用 upper_bound右端点用 lower_bound输出顺序不对没有按渔民输入顺序输出查询循环按 xs 原顺序遍历其中最常见的是第一种。很多初学者生成区间前不做 y L 的过滤导致鱼在垂直距离上已经够不到但水平区间还是生成了统计时被错误算入。这属于对题意的理解不完整建议读题时看到“距离不超过 L”就应该意识到这是二维距离约束而不仅仅是水平方向。4.4 信奥刷题打卡的一点个人心得这题我写完后最大的感受是信奥里很多题的难度不在数据结构和算法本身而在“把题面抽象成什么模型”。你如果第一眼就从点距离入手很容易陷进计算几何的套路里但一旦想到把鱼变成区间整道题瞬间变成了一道基础排序二分题。这种抽象能力没有捷径只能靠多做题、多见模型来积累。所以我比较推荐刷题打卡的时候不要只满足于 AC而是把每次想到的模型转化过程简要记在题解或者笔记里哪怕一两句话也好。过三个月回看会发现自己对题型的敏感度提升非常明显。另外一个经验是写完提交前务必自己构造一两组小样例手算验证。很多 WA 都是边界逻辑错误这些错误在随机样例里未必触发但在 OJ 的数据点里就一定会出现。把测试意识变成习惯比多刷一百道题更能提高正确率。