企业官网建设流程全解析

今天打卡到第2946题，正好是 P5867 [SEERC 2018] Fishermen。这题我此前在好几个信奥交流群里见人提过，一直没认真做，这次趁着刷题进度排到它，完整推了一遍。题目本身不复杂，但思维转化的过程非常典型，很适合用来练“几何问题转区间问题”这一套路。整道题的核心就一句话：把一条鱼能被哪些渔民钓到，看成一个区间，然后离线排序、二分计数。就这么个思路，能把 O(NM) 的暴力降到 O((N+M) log(N+M))，在 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 都只有 1e4，1e8 的运算量也已经很勉强了。

所以必须把复杂度降下来。区间转化之后，问题就变成了一个非常经典的“离线查询”模型。为什么叫离线？因为我们可以先把所有鱼的区间准备好，再把所有渔民的坐标准备好，统一排序处理，而不是每来一个渔民都重新扫一遍所有鱼。这种把所有查询收集起来一次性处理的思路，在信奥里叫离线化处理，是处理大批量查询问题的基本盘。

顺着这个思路，核心目标就变成：快速回答 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 的区间有三个（三个区间的左端点都 ≤ 1），r < 1 的区间只有一个（[0, 0] 的右端点 0 < 1），3 减 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((N+M) 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 得莫名其妙。既然涉及距离平方，中间值最大是 1e18，long 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 + 1，mid * 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; vector<FishInterval> 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}); } vector<long long> xs(M); for (int i = 0; i < M; i++) { cin >> xs[i]; } vector<long 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((N+M) log N)，空间复杂度 O(N)。

4. 常见问题与调试心得

4.1 边界数据：鱼刚好在竿长边界

很多人做题时不会故意构造边界数据，导致一些隐藏问题在本地样例上根本暴露不出来。拿这道题来说，边界情况有两种值得专门测。第一种是 y 恰好等于 L，此时 d = 0，w = 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 = -5，w = 3，左端点是 -8。这没有任何问题，排序时负数默认在最前面，upper_bound 和 lower_bound 处理的是迭代器区间，不关心元素本身是否非负。不需要做偏移或离散化，用 long long 原样保持即可。

有一点需要提醒：如果你做的是“把坐标轴偏移到非负再差分”那类做法，就要小心处理负数坐标和偏移量。但本题用的是排序二分，天然不受负数影响，这点也是我偏爱这个做法的原因之一，逻辑上少一层转换就少一个出错点。

4.3 多次提交最常见的错误

把容易踩的坑集中整理成一张速查表，方便提交前逐一自检：

其中最常见的是第一种。很多初学者生成区间前不做 y > L 的过滤，导致鱼在垂直距离上已经够不到，但水平区间还是生成了，统计时被错误算入。这属于对题意的理解不完整，建议读题时看到“距离不超过 L”就应该意识到这是二维距离约束，而不仅仅是水平方向。

4.4 信奥刷题打卡的一点个人心得

这题我写完后最大的感受是，信奥里很多题的难度不在数据结构和算法本身，而在“把题面抽象成什么模型”。你如果第一眼就从点距离入手，很容易陷进计算几何的套路里；但一旦想到把鱼变成区间，整道题瞬间变成了一道基础排序二分题。这种抽象能力没有捷径，只能靠多做题、多见模型来积累。所以我比较推荐刷题打卡的时候，不要只满足于 AC，而是把每次想到的模型转化过程简要记在题解或者笔记里，哪怕一两句话也好。过三个月回看，会发现自己对题型的敏感度提升非常明显。

另外一个经验是写完提交前，务必自己构造一两组小样例手算验证。很多 WA 都是边界逻辑错误，这些错误在随机样例里未必触发，但在 OJ 的数据点里就一定会出现。把测试意识变成习惯，比多刷一百道题更能提高正确率。