第一次看到 P1296 奶牛的耳语 这道题的时候我几乎是被标题骗过去的一排奶牛站在数轴上想知道哪些能互相说悄悄话随手一个双层循环样例秒过心里还挺美。交上去才发现数据规模根本不给你暴力活路。重新读题之后我才意识到这道题真正要练的不是“会不会枚举”而是你能不能把一个看似成立的简单条件拆成两个独立的关键字再用区间统计的手段去加速。下面我会从题意建模开始依次讲清楚暴力为什么会超时、为什么常规双指针在这里会翻车以及离线树状数组这个经典方案的完整推导和 AC 代码。无论你是在准备 CSP/NOIP、考研机试还是单纯刷题这套“按坐标排序 按阈值离线 BIT 统计”的组合都值得记在脑子里。先说明一个容易让题解对不上的地方这道题在不同 OJ 上的数据版本不完全一样最常见的是“每头奶牛有各自的听力值”也有少数版本给的是全局距离 D。我下面先讲前者它的模型更通用解法也能覆盖后者如果你遇到的是全局 D 的版本直接看第六节那个退化写法就行。1. “互相耳语”的条件到底是距离还是听力先把题意翻译成不等式1.1 “能听到”和“能互听”差了一个 min假设奶牛 i 站在 (x_i)听力范围是 (h_i)有的题面写作 (d_i)。它能听到奶牛 j 的耳语当且仅当两个位置之间的距离不超过 (h_i)也就是[ |x_i-x_j| \le h_i ]反过来j 要听到 i需要满足[ |x_i-x_j| \le h_j ]两头奶牛“互相耳语”必须同时满足这两个不等式。两个上界里一定有一个更小所以整个条件等价于[ |x_i-x_j| \le \min(h_i,h_j) ]生活里有个很直接的类比两个人交头接耳一个耳朵不好使、一个耳朵好使决定能不能听清的是耳朵差的那个。听力好并不能把距离拉远听力差的人才是瓶颈。这一小段公式是整道题的题眼。很多题解上来就是“排序之后枚举”但如果不先把 min 这个逻辑想透后面优化方向很容易跑偏甚至写出来的代码统计的其实是“单向耳语”而不是“互听”。1.2 一个典型测试用例长什么样输入一般长这样3 0 1 2 3 4 2第一行是奶牛数量随后每行是位置 x 和听力 h有的版本把两个数顺序反过来做题前先看清楚。目标输出一个整数表示能互相耳语的奶牛对数。手算这组数据位置 0听力 1和位置 2听力 3距离 2(min(1,3)1)听不到位置 0 和位置 4听力 2距离 4(min(1,2)1)听不到位置 2听力 3和位置 4听力 2距离 2(min(3,2)2)距离恰好等于 2能听到。所以答案是 1。这里有个细节题目里说“不超过”时等于条件必须算进去。后面写代码时upper_bound、、这些符号都会围绕这个“等于”做文章错一个符号答案就可能偏小。这类题常见的数据范围是 (N) 可以到 (10^5)坐标和听力都可能到 (10^9) 甚至更大。如果题目没给范围按最坏情况准备 O(N log N) 的解法总没错否则很容易在某个大样例上卡死。1.3 初读时三个常见理解偏差单向当双向只判断 i 能否听到 j忽略反过来也要成立。这样统计出来的对数会偏大。很多新手写完暴力之后样例能过是因为样例里恰好没有这种“单向成立”的干扰对。只查相邻位置认为只有排完序后位置相邻的牛才可能互听。实际上两头牛中间可以隔着别的牛只要距离和听力满足条件就构成一对。排序是为了方便统计不是为了只检查相邻项。把 min 当成 max有人会想“只要两头牛里有一头听力足够好就能互相听到”。这是错的。听力好的人能听到你不代表你也能听到他悄悄话传不回去。这些偏差在小数据上经常试不出来因为答案恰好一样数据一复杂就变 WA。2. 暴力枚举先跑通排序到底改变了什么2.1 排序让绝对距离变成前缀距离统计的是无序数对顺序本身无所谓。先把所有奶牛按坐标从小到大排序。排序之后对于任意 i j两头牛之间的距离就是 (x_j-x_i)一定是非负数代码里完全不用写 abs。这个预处理看起来不起眼其实很重要坐标一旦有序距离就变成单调可二分的前缀概念后续所有优化都建立在它之上。就算原本坐标可能相同排序后也能保证相同位置的两头牛相邻程序里自然覆盖“距离 0”的情况。2.2 暴力写法和复杂度暴力思路很直接读入每一头牛的(位置, 听力)。按位置排序。双重循环枚举所有 i j。如果x[j] - x[i] min(h[i], h[j])答案加一。C 代码长这样#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorpairlong long, long long a(n); for (int i 0; i n; i) { cin a[i].first a[i].second; // 位置, 听力 } sort(a.begin(), a.end()); long long ans 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { long long dis a[j].first - a[i].first; if (dis min(a[i].second, a[j].second)) { ans; } } } cout ans \n; return 0; }复杂度是 (O(N^2))。N 在 5000 以内可以接受N 一旦到 (10^5)(10^{10}) 次比较无论如何都会超时。所以暴力只能用来对拍不能当最终解法。2.3 暴力中重复浪费在哪里从暴力内部视角观察对于固定 ij 从 i1 开始递增距离不断变大。第一个条件 (x_j-x_i \le h_i) 其实限制的是一个连续前缀区间一旦某个 j 已经超过 (h_i)后面的 j 更不可能被 i 听到可以直接 break。这是第一层可以省掉的浪费。但第二个条件 (x_j-x_i \le h_j) 等价于 (x_jh_j \ge x_i)它和 j 自身的听力有关并不随 j 单调递增。也就是说对每个 i右侧“够得着”的牛形成一段连续区间但区间内还需要根据另一个与 j 相关的条件做过滤。这有点像“先划出一个活动范围再在这个范围内点名查资质”。活动范围可以很快算出来真正麻烦的是第二层过滤。想要优化必须把两件事分开一是快速找出满足第一个条件的右边界二是在这个边界内统计同时满足第二个条件的数量。3. 双指针陷阱右边界为什么不单调3.1 看起来很美的滑动窗口很多人熟悉“找出所有点对距离不超过 D”的双指针模板排序后维护一个右指针左指针每右移一位右指针只增不减窗口内所有点对一次统计完。于是想当然套到这道题上。但这个模板能成立的根本前提是限制距离 D 对所有左端点都是同一个常数。本题每头牛的听力值不同对每个 i 的合法右边界是[ R_i \max{j \mid x_j-x_i \le h_i} ]由于 (h_i) 各不相同(R_i) 作为 i 的函数并不保证单调递增。举个反例牛 A位置 0听力 100000牛 B位置 1听力 1牛 C位置 100000听力很大。排序后位置 0 这头牛的右边界可以延伸很远几乎到数组末尾但位置 1 这头牛听力只有 1它的右边界也许只到位置 2。如果照搬普通双指针模板右指针只增不减就会把牛 C 一直留在牛 B 的窗口里导致多算一堆不满足条件的配对。3.2 用二分锁定右边界而不是滑窗因为 x 已经有序对每个 i条件 (x_j-x_i \le h_i) 等价于 (x_j \le x_ih_i)。直接对数组 x 做upper_bound就能找到最后一个满足条件的下标[ R_i \text{upper_bound}(x, x_ih_i) - 1 ]这一步是 (O(\log N))每头牛独立计算不受别的牛听力影响所以绝对正确。即使 (h_i) 非常大或者等于 0都能正确处理。C 里写法是int R int(upper_bound(x.begin() i, x.end(), x[i] h[i]) - x.begin()) - 1;注意必须用upper_bound而不是lower_bound因为要的是“小于等于”等于边界也要算进去。R 至少会是 i因为 (x_ih_i \ge x_i) 恒成立所以查询区间写作 [i1, R]有可能为空。3.3 问题最终形态区间内按值过滤把两个条件合并后对每头奶牛 i真正要回答的问题是在奶牛下标区间 ((i, R_i]) 里存在多少头奶牛 j满足 (x_jh_j \ge x_i)这里的“区间”由坐标和 i 的听力决定“值过滤”由 (x_i) 决定。两者交织在一起无法靠单纯排序、二分或者一个单调指针直接完成。但我们可以把查询离线用一个支持区间求和的容器来“边加点边询问”这就有了下一章的做法。4. 离线处理加上树状数组区间内按阈值统计的通用打法4.1 主线思路按阈值从大到小“点亮”奶牛定义每头奶牛 j 的一个关键值[ y_j x_jh_j ]第二个条件 (x_jh_j \ge x_i) 就变成 (y_j \ge x_i)。现在想象有一张表格每个下标 j 对应一个开关只有 (y_j \ge x_i) 时开关才打开。一次查询就变成数区间 ((i,R_i]) 里开关打开的数量。问题是怎么高效地让开关按需开合因为不同查询的 (x_i) 不一样。离线排序是关键把所有查询按 (x_i) 从大到小排。同时把奶牛按 (y_j) 从大到小排。每次处理一个新查询之前把所有 (y_j \ge) 当前查询阈值 (x_i) 的奶牛开关打开在树状数组对应的下标位置加一。因为查询的阈值是从大到小遍历的阈值只会越来越低已经打开的开关不需要再关闭所以整个过程只需要加点不需要删点。这样做完之后每个查询就变成一个标准的树状数组区间求和query(R_i) - query(i)。你可以把它类比成“查某个分数段有多少人”先把够分的人名字都写在名单上再数名单上落在指定编号区间的有多少人。名单只会越来越长所以整个过程可以做得很顺。4.2 为什么选 Fenwick 树这里需要的操作是单点加一按下标 j 位置加一求前缀和进而算区间和。Fenwick 树两种操作都是 (O(\log N))常数小、代码短是首选。平衡树或者线段树也能做但没必要。注意我们按下标排序后的位置序号建 BIT不是按 (y_j) 的值建因此不需要对坐标离散化也不需要对听力值离散化。4.3 算法步骤与正确性证明完整步骤读入所有奶牛按 x 排序存为数组 x 和 h下标从 0 开始。对每头 i 求右边界 (R_i \text{upper_bound}(x_ih_i) - 1)。生成查询结构体包含阈值 x_i、左端点 Li1、右端点 R_i。如果 L R说明这头牛右侧没有候选跳过。把查询按 x_i 降序排序。把奶牛 j 按 (y_j x_jh_j) 降序排序得到一个顺序表。用一个指针 p 从 0 开始扫这个降序奶牛表。遍历每个查询 q先把表中所有 (y_j \ge q.x_i) 的奶牛在 BIT 下标 j 处加一然后ans BIT.query(q.R) - BIT.query(q.L - 1)。输出 ans。正确性分两点看不重每对 (i,j) 只会被 i 的查询统计一次因为查询区间只取右侧 j i。遍历到 j 的时候它不会回头把 i 当成右侧配对。不漏如果 (i,j) 满足互听条件且 j i那么 j 一定满足 (x_j \le x_ih_i)所以 j 一定落在区间 (i,R_i] 内同时它满足 (y_j \ge x_i)所以在处理 i 的查询时j 已经在 BIT 中点亮必然被区间和计入。反过来被计入的 j 也都满足两个条件构成合法对。坐标相同的情况也不用慌不同编号的牛坐标相同排序后相对顺序确定右侧那头会被左侧计数。距离是 0只要听力值不为负就满足互听条件BIT 的加点与查询逻辑自然覆盖。5. 完整 AC 代码与最容易错的四个细节5.1 C 完整实现#include bits/stdc.h using namespace std; struct Query { long long th; // x_i int L, R; // 统计下标范围 [L, R] }; struct Fenwick { int n; vectorint c; Fenwick(int n) : n(n), c(n 1, 0) {} void add(int idx, int val) { // idx 从 0 开始 for (int i idx 1; i n; i i -i) { c[i] val; } } long long prefix(int cnt) { // 前 cnt 个元素之和下标 [0, cnt-1] long long s 0; for (int i cnt; i 0; i - i -i) { s c[i]; } return s; } long long rangeSum(int l, int r) { // 闭区间 [l, r] return prefix(r 1) - prefix(l); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; if (!(cin n)) return 0; vectorpairlong long, long long a(n); for (int i 0; i n; i) { cin a[i].first a[i].second; // 位置, 听力 } sort(a.begin(), a.end()); vectorlong long x(n), h(n); for (int i 0; i n; i) { x[i] a[i].first; h[i] a[i].second; } vectorQuery queries; queries.reserve(n); for (int i 0; i n; i) { int R int(upper_bound(x.begin() i, x.end(), x[i] h[i]) - x.begin()) - 1; if (i 1 R) { queries.push_back({x[i], i 1, R}); } } sort(queries.begin(), queries.end(), [](const Query p, const Query q) { return p.th q.th; }); vectorint order(n); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [](int i, int j) { long long yi x[i] h[i]; long long yj x[j] h[j]; if (yi ! yj) return yi yj; return i j; }); Fenwick bit(n); long long ans 0; int ptr 0; for (const auto q : queries) { while (ptr n x[order[ptr]] h[order[ptr]] q.th) { bit.add(order[ptr], 1); ptr; } ans bit.rangeSum(q.L, q.R); } cout ans \n; return 0; }这段代码我实际跑过几个关键位置都做了注释。排序后数组下标不变BIT 加点和区间查询用的都是排序后的位置序号所以逻辑非常干净。5.2 四个最容易 WA 的细节第一个细节是long long。坐标和听力都能到 (10^9)(x_ih_i) 可能达到 (2 \times 10^9) 甚至更大用 int 会溢出。答案最大值是 (N(N-1)/2)当 (N10^5) 时大约是 (5 \times 10^9)同样超出 int 范围。所以 x、h、ans 全部用long long是最稳的。第二个细节是upper_bound的边界。要找的是最后一个满足 (x_j \le x_ih_i) 的下标所以必须用upper_bound。如果误用lower_bound等于条件会被漏掉答案偏小。等号情况在这类题里非常常见比如第 5.1 节测试数据里位置 2 和位置 4 那对距离刚好等于 min漏掉就 WA。第三个细节是查询排序与加入顺序。查询按 (x_i) 降序奶牛点按 (y_j) 降序处理查询前把所有 (y_j \ge x_i) 的点加入。注意“大于等于”要包含等于排序比较时也是。如果漏掉等号所有“距离刚好等于”的配对都会消失。第四个细节是去重。程序里每个 i 只统计右侧区间所以不会把 (i,j) 和 (j,i) 算两次。千万别一开始把全体奶牛都加进 BIT那样左端点也会被统计进去答案会明显偏大。5.3 暴力对拍的参考方式写优化解之前强烈建议先写一份暴力程序。然后随机生成小数据对拍(N) 在 1 到 8 之间位置在 0 到 20 之间随机听力在 0 到 10 之间随机分别跑暴力和优化解法比对输出。比如前面那个例子3 0 1 2 3 4 2暴力输出 1优化解法也必须输出 1。对拍脚本只要发现一次不一致就把数据打出来查是符号问题还是排序问题。我每次写这种“区间内按值过滤”的题都是先暴力后优化排查效率会高很多。6. 如果原题变成“所有奶牛听力相同”的版本模型立刻退化6.1 固定听力的双指针写法如果所有奶牛听力都是同一个全局距离 D那么条件直接变成 (x_j-x_i \le D)和第二个关键字无关。这时候连 BIT 都不需要普通双指针足够。排序后维护一个右指针 r对于每个左端点 i把 r 向右扩展到边界然后答案加r - i。因为随着 i 增加右边界只增不减这个双指针模板才能成立。long long ans 0; int r 0; for (int i 0; i n; i) { if (r i) r i; while (r 1 n a[r 1].first - a[i].first D) { r; } ans r - i; } cout ans \n;每个 i 统计的是右边界内所有 j i天然去重复杂度 (O(N))。但这个简单写法的成立完全依赖“D 全局不变”遇到每头牛听力不同的版本千万不要硬套。6.2 同模型的推广空间“在坐标区间内统计满足 (y_j \ge x_i) 的点数”这个二维偏序模型其实可以解决很多问题区间内某个值域的数量统计求数组中“位置差不超过 A_i 且满足另一属性条件”的点对总数二维平面上“左下区域点数统计”的一维退化版本某些带左右边界约束的双关键字计数问题。把 P1296 吃透等于掌握了一个离线二维偏序的通用模板一维用排序另一维用 BIT。以后看到“N 个点每个点带两个关键字问满足某种不对称条件的点对数量”可以直接往这个方向想而不是老想着怎么套嵌套循环。我在不同 OJ 上写过这道题的多个版本现在的习惯是先写暴力当对拍器再用离线 BIT 写正解整个调试过程会顺很多。还有一个小技巧做题前先把所有“等于”的情况列出来upper_bound、、逐个核对。这类题绝大多数 WA都挂在你想当然的那个等号上。希望这篇题解能帮你少走点弯路。