题目来源：改编自 洛谷 P1102 A-B 数对。本 Lab 使用课程自定义输入输出协议和独立测试，不复制来源站点的代码或测试。

学习目标

• 把"枚举全部数对"的 $O(n^2)$ 问题转化为"对每个值二分统计目标值出现次数"的 $O(n\log n)$ 问题；
• 正确书写 lower_bound/upper_bound 式的二分计数，并处理 a[i] + c 超出 int 范围的溢出隐患；
• 用 64 位整数累计答案，解释答案为什么可达 $n^2$ 量级。

前置知识与环境

先阅读第 8.1 节 基础查找与折半查找的"折半查找前提"与"折半查找算法"两节：本 Lab 的序列初始无序，需要先排序再折半，正好对应"预处理 + 多次查找"的摊还视角。

在 Lab 目录执行 make doctor 检查环境；未安装 Make 时可在仓库根使用 pnpm 兜底命令（见下文"运行"）。

任务

给定 n 个整数与目标差 c，统计满足 a_i − a_j = c 的有序下标对 (i, j) 的个数。约定：

• 不同位置算不同数对，即使两处数值相同；
• i 与 j 可以相同——因此 c = 0 时每个下标与自己恰好构成一对（全相同时答案为 $n^2$）。

输入格式

• 第一行：两个整数 n 和 c；
• 第二行：n 个整数（顺序即下标顺序，下标从 1 开始）。

输出格式

一行一个整数：满足 a_i − a_j = c 的有序数对个数。答案可达 $n^2$ 量级，需用 64 位整数计算与输出。

数据范围与限制

项目	范围
元素个数 n	1 ≤ n ≤ 2×10⁵
目标差 c	|c| ≤ 10⁹
元素取值	|元素| ≤ 10⁹
时间复杂度要求	排序 + n 次二分，$O(n\log n)$；$O(n^2)$ 枚举全部数对会在压力用例超时
输出上限	1 MB（单个 64 位整数，默认上限足够）

正常、边界与错误情况

• 正常：重复值按位置计数，一个 A 位置可以匹配多个等值的 B 位置；
• 边界：c = 0 且全部元素相同（答案 $n^2$）；c 为负数；元素为负数；a[i] + c 可达 ±2×10⁹，超出 int 范围；
• 无解：不存在任何满足条件的数对时输出 0。

样例

样例 1

4 1
1 1 2 3

3

A − B = 1 的有序数对：A = 2 可配两个不同位置的 B = 1（2 对），A = 3 可配 B = 2（1 对），合计 3。

样例 2

6 -2
-5 -3 -3 -1 1 1

6

A = B − 2：两个位置的 B = −3 各配到 A = −5（2 对）；B = −1 配到两个位置的 A = −3（2 对）；两个位置的 B = 1 各配到 A = −1（2 对）；合计 6。

实现提示

把 A − B = c 改写成 A = B + c：排序一份副本，对序列中每个值 x（枚举的是 B），用二分统计 x + c 在有序数组中的出现次数，即 upper_bound(x + c) − lower_bound(x + c)，累加到 64 位答案里。

两个易错点：

• x + c 最大可达 $2\times {10}^9$，超出 int 表示范围，目标值要用 long long 存放；
• 累加器必须是 long long——c = 0 且全相同时答案为 $n^2=4\times {10}^{10}$，int 会静默溢出。

按值建散列表计数能做到平均 $O(n)$，但散列将在第 9 章展开，本 Lab 先用"排序 + 二分"实现。

运行

make run
# 免 Make 兜底：在仓库根执行
pnpm lab:run -- labs/chapter-08/exercise/E-08-04-count-diff-pairs

需要单用例或严格评分时使用 make run CASE=005-stress-2e5 与 make score；也可用 pnpm lab:score -- labs/chapter-08/exercise/E-08-04-count-diff-pairs 兜底。

完成清单

• 样例 1、样例 2 与 make run 全部用例通过；
• c = 0 且全相同时输出 $n^2$（含每个下标与自己的一对）；
• a[i] + c 与答案累计都使用 long long，无静默溢出；
• 压力用例（n = 2×10⁵）在时限内完成，能说出 $O(n^2)$ 枚举约需 $4\times {10}^{10}$ 次比较为何必然超时。

思考与复盘

1. 若把约定改成"i ≠ j（排除自身配对）"，二分计数法应如何修正？c = 0 时答案从 $n^2$ 变成什么？
2. "对每个值二分 x + c"枚举的是 B，"对每个值二分 x − c"枚举的是 A——为什么两种数法结果一定相同？
3. 排序二分的 $O(n\log n)$ 与散列表的平均 $O(n)$，在什么前提下后者才真正更优？有序数组在"多次查询不同 c"的场景下还有什么好处？