哈希表方案思考

核心转换

• 问题：找满足 A - B = C 的数对
• 转换为：A = B + C
• 对于每个 B，我们需要查找是否存在 B + C

算法步骤

第一步：建立频率哈希表

扫描一遍数列，用 map 或 unordered_map 记录每个数字出现的频率：

• key：数字本身
• value：出现次数

第二步：遍历每个数字B，查找对应的A

对数列中的每个数字 B（作为减数）：

• 计算 A = B + C（被减数）
• 在哈希表中查询 A 是否存在
• 如果存在，加上 A 的频率到答案中

简单示例演算

数列：1 1 2 3，C = 1

第一步：建立哈希表

{1: 2, 2: 1, 3: 1}

第二步：遍历查找

- B=1(第1个): 需要A=2，哈希表中2出现1次 → 答案 += 1
- B=1(第2个): 需要A=2，哈希表中2出现1次 → 答案 += 1
- B=2(第3个): 需要A=3，哈希表中3出现1次 → 答案 += 1
- B=3(第4个): 需要A=4，哈希表中无4 → 答案 += 0

答案 = 1 + 1 + 1 + 0 = 3 ✓

---

复杂例子：数字重复且位置混乱

数列：1 1 2 3 2 4，C = 1

第一步：建立哈希表

{
  1: 2,    // 1出现2次
  2: 2,    // 2出现2次
  3: 1,    // 3出现1次
  4: 1     // 4出现1次
}

第二步：遍历每个B，查找对应的A

对每个B的出现位置进行遍历：

B=1(位置1): 需要A=2，哈希表中2出现2次 → 答案 += 2
           (配对：(2[位置3], 1[位置1]) 和 (2[位置5], 1[位置1]))

B=1(位置2): 需要A=2，哈希表中2出现2次 → 答案 += 2
           (配对：(2[位置3], 1[位置2]) 和 (2[位置5], 1[位置2]))

B=2(位置3): 需要A=3，哈希表中3出现1次 → 答案 += 1
           (配对：(3[位置4], 2[位置3]))

B=3(位置4): 需要A=4，哈希表中4出现1次 → 答案 += 1
           (配对：(4[位置6], 3[位置4]))

B=2(位置5): 需要A=3，哈希表中3出现1次 → 答案 += 1
           (配对：(3[位置4], 2[位置5]))

B=4(位置6): 需要A=5，哈希表中无5 → 答案 += 0

答案 = 2 + 2 + 1 + 1 + 1 + 0 = 7

为什么这样想？

数对的定义

"不同位置的数字一样的数对算不同的数对"意味着：

• (A的位置, B的位置) 是数对的唯一标识
• 位置在前还是在后完全不影响

频率的作用

• 当 B 出现多次时，每个 B 都能和所有符合条件的 A 配对
• 当 A 出现多次时，每个 B 都能和每个 A 配对
• 结果自动累加：B的频率 × A的频率

简化理解

不遍历每个位置，直接用频率计算：

答案 = ∑(每种不同的B值) [B值在哈希表中的频率 × 对应A值在哈希表中的频率]

对于 1 1 2 3 2 4, C=1:
- B值为1时：A值为2，B频率=2，A频率=2，贡献 2×2 = 4
- B值为2时：A值为3，B频率=2，A频率=1，贡献 2×1 = 2
- B值为3时：A值为4，B频率=1，A频率=1，贡献 1×1 = 1
- B值为4时：A值为5，B频率=1，A频率=0，贡献 1×0 = 0

总答案 = 4 + 2 + 1 + 0 = 7 ✓

---

核心要点

✓ 哈希表自动处理了重复和位置问题——通过频率计数，每一对 (值A, 值B) 的组合都被准确地计数了！

✓ 时间复杂度： O(N log N)（使用 map，查找为 log N）或 O(N)（使用 unordered_map）

✓ 空间复杂度： O(N)

✓ 实现细节： 用 long long 作为key，因为 aᵢ < 2³⁰，相加可能超过 int 范围

---

时间复杂度详细分析

使用 map<long long, long long> 的情况

第一步：建立频率哈希表

for (int i = 0; i < n; i++) {
    cin >> arr[i];
    freq[arr[i]]++;
}

• 读入 n 个数字：O(n)
• 每次 freq[arr[i]]++ 操作：O(log n)（map 的插入/查找）
• 第一步总时间：O(n log n)

第二步：遍历查找并累加

for (int i = 0; i < n; i++) {
    long long b = arr[i];
    long long a = b + c;
    if (freq.find(a) != freq.end()) {
        ans += freq[a];
    }
}

• 循环 n 次
• 每次 freq.find(a) 查找：O(log n)
• 第二步总时间：O(n log n)

总时间复杂度

$$T = O(n \log n) + O(n \log n) = O(n \log n)$$

使用 unordered_map<long long, long long> 的情况

若用 unordered_map 替代 map：

• 平均每次插入/查找：O(1)
• 第一步：O(n)
• 第二步：O(n)
• 总时间复杂度：O(n)（平均情况）
• 最坏情况：O(n²)（hash 冲突严重时）

复杂度对比

容器	第一步	第二步	总复杂度	适用场景
map	O(n log n)			数据量大且要求稳定
unordered_map	O(n)		O(n) 平均	一般情况，性能更好

与暴力算法的对比

暴力算法（两层循环）：

long long ans = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (arr[i] - arr[j] == c) {
            ans++;
        }
    }
}
// 时间复杂度：O(n²)

哈希表算法：

// 时间复杂度：O(n log n) 或 O(n)

数据量验证

对于本题 N ≤ 2×10⁵：

• 暴力算法：(2×10⁵)² = 4×10¹⁰ 次操作 ❌ 会超时
• 哈希表算法：
  • 用 map：2×10⁵ × log(2×10⁵) ≈ 2×10⁵ × 18 ≈ 3.6×10⁶ 次操作 ✓
  • 用 unordered_map：2×10⁵ 次操作 ✓

结论： 哈希表算法能轻松处理最大数据量，而暴力算法会明显超时

---

C++ 实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    long long c;
    cin >> n >> c;
    
    map<long long, long long> freq;
    vector<long long> arr(n);
    
    // 第一步：读入数据并记录每个数字的频率
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        freq[arr[i]]++;
    }
    
    // 第二步：遍历每个B，查找对应的A = B + C
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long b = arr[i];
        long long a = b + c;
        // 如果A存在于哈希表中，加上A的频率
        if (freq.find(a) != freq.end()) {
            ans += freq[a];
        }
    }
    
    cout << ans << endl;
    return 0;
}

代码逻辑解释

1. 读入阶段：

   • 读入 n 和 c
   • 读入 n 个数字到数组 arr 中
   • 同时用 map 统计每个数字的出现频率

2. 计算阶段：

   • 遍历数组中的每个数字作为 B
   • 计算需要找的数字 A = B + C
   • 在哈希表中查询 A 是否存在
   • 如果存在，将 A 的频率加到答案中

3. 输出：打印最终答案

关键优化

• ios_base::sync_with_stdio(false); cin.tie(NULL); 加速输入输出
• 使用 map 而不是二维数组循环，避免 O(N²) 的时间复杂度
• 一遍遍历即可完成计算，无需多次查询

---

关键语法详解：freq.find(a) != freq.end()

这行代码的含义

if (freq.find(a) != freq.end()) {
    ans += freq[a];
}

这是在 检查哈希表中是否存在键 a

详细拆解

freq.find(a) 返回什么？

• 找到键 a：返回指向该元素的迭代器
• 未找到键 a：返回 end() 迭代器（指向容器末尾之后的哨兵位置）

freq.end() 是什么？

• 指向 map 容器的末尾之后的位置
• 不指向任何真实元素，仅作为"查询失败"的标志

!= 的含义

freq.find(a) != freq.end()

如果返回的迭代器不等于 end()，说明找到了这个键 a，执行 if 块

三种常见写法对比

方法1：用 find() 和 end()（推荐）

if (freq.find(a) != freq.end()) {
    ans += freq[a];
}

• ✓ 先检查存在性，再访问
• ✓ 不会自动创建新键
• ✓ 最安全的做法

方法2：用 count()（简洁）

if (freq.count(a)) {
    ans += freq[a];
}

• count() 返回 0（不存在）或 1（存在）
• 等价于方法1，代码更简洁
• 也不会创建新键

方法3：直接访问（不推荐）

if (freq[a]) {  // ❌ 有风险
    ans += freq[a];
}

• ❌ 如果键不存在，会自动创建该键并初始化为 0
• 虽然在本题中逻辑还是对的，但会浪费内存
• 不是最佳实践

本题具体例子

数列：1 1 2 3，C = 1

// 哈希表内容：{1: 2, 2: 1, 3: 1}

// 当处理 B = 1 时
a = 1 + 1 = 2
freq.find(2)                    // 查找键 2
↓
找到了！返回指向 (2→1) 的迭代器

freq.find(2) != freq.end()      // 判断：true
↓
ans += freq[2]                  // 执行：ans += 1

---

// 当处理 B = 3 时
a = 3 + 1 = 4
freq.find(4)                    // 查找键 4
↓
没找到！返回 end() 迭代器

freq.find(4) != freq.end()      // 判断：false
↓
不执行 if 块

为什么选择 find() 而不是直接访问？

对比演示：

// 场景：查找键 100（不存在）

// 方法1：find()（推荐）
if (freq.find(100) != freq.end()) { ... }
// 结果：只查询，freq 的大小不变

// 方法3：直接访问（不推荐）
if (freq[100]) { ... }
// 结果：自动创建 freq[100] = 0，freq 的大小 +1
// 额外消耗内存！

结论： 对于纯查询场景（不需要插入新键），find() 是最安全高效的选择！

写出暴力导致TLE的解法代码

当然可以。对于这道题，最直观的暴力解法就是使用两层循环，不进行任何优化，直接枚举所有的数对 $(A, B)$。

这种解法的时间复杂度是 $O(N^2)$，当 $N$ 的规模达到 $2 \times 10^5$ 时，$N^2$ 约为 $4 \times 10^{10}$，这会远远超过一般在线评测系统（OJ）每秒 $10^8$ 次左右的计算能力上限，因此会导致超时 (Time Limit Exceeded, TLE)。

写出并理解 TLE 版本是学习算法优化的第一步，因为它能让你清晰地看到问题的“朴素”解法是什么，从而思考如何针对性地进行优化。

---

暴力 $O(N^2)$ TLE 代码 (C++)

这个版本的代码思路非常简单：

1. 读入所有数据。
2. 第一层循环 for i from 0 to n-1，枚举每一个数 a[i] 作为数对中的 $A$。
3. 第二层循环 for j from 0 to n-1，枚举每一个数 a[j] 作为数对中的 $B$。
4. 为了避免把自己和自己组成数对（除非题目允许且有多个相同数字），加上判断 if (i == j) continue;。
5. 判断 if (a[i] - a[j] == C) 是否成立，如果成立，则计数器加一。
6. 输出最终的计数器。

#include <iostream>
#include <vector>

// 使用 long long 来存储计数器，防止结果溢出
// 虽然在这份 TLE 代码中可能遇不到那么大的结果，但这是个好习惯
using ll = long long;

int main() {
    // 尽管会 TLE, IO 优化还是可以写上
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    ll c;
    std::cin >> n >> c;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    ll count = 0;

    // 外层循环，枚举每个元素 a[i] 作为 A
    for (int i = 0; i < n; ++i) {
        // 内层循环，枚举每个元素 a[j] 作为 B
        for (int j = 0; j < n; ++j) {
            
            // 题目要求：“不同位置的数字一样的数对算不同的数对”
            // 这意味着 a[0] 和 a[1] 即使值相同，也是不同的位置。
            // 因此，我们不需要跳过 i == j 的情况，因为题目并没有说A和B必须是不同位置的数
            // 如果题目要求是不同位置，则需要 if(i == j) continue;
            // 按照题意，a[i] 和 a[i] 自己也可以组成一对，如果 a[i] - a[i] == C
            
            // 检查差值是否等于 C
            // 注意：a[i] 和 c 的类型可能是 int 和 long long，
            // 为了避免隐式转换可能带来的问题，显式地进行类型转换
            if ((ll)a[i] - (ll)a[j] == c) {
                count++;
            }
        }
    }

    std::cout << count << std::endl;

    return 0;
}

为什么这份代码会 TLE？

• 循环次数：代码的核心是两层嵌套的 for 循环。外层循环执行 $N$ 次，内层循环也执行 $N$ 次。总的判断次数是 $N \times N = N^2$ 次。
• 数据规模：
  • 对于 $75\%$ 的数据，$N \le 2000$。$N^2 = 4 \times 10^6$，这个计算量在 1 秒内通常是可以接受的。所以这份代码能通过一部分测试点。
  • 对于 $100\%$ 的数据，$N \le 2 \times 10^5$。$N^2 = (2 \times 10^5)^2 = 4 \times 10^{10}$。这个计算量是巨大的，远远超出了时限。

教练点评： 这份代码就是你思考这道题时的“原点”。所有更优的算法，无论是排序+二分还是排序+双指针，都是为了优化内层的这一个循环——将原本 $O(N)$ 的查找过程，降低到 $O(\log N)$（二分）或者均摊 $O(1)$（双指针）。这就是算法优化的本质。

好的，没问题。

这里提供一个功能完整的数据生成器。它会生成 10 组测试数据（1.in/1.out 到 10.in/10.out），并且测试点设计考虑了各种边界情况和数据分布，非常适合用于搭建 OJ。

数据生成器功能说明

1. 内置标准解法：生成器内部包含了 排序 + 二分 的 $O(N \log N)$ 标准解法，用于计算并生成正确的 .out 文件。
2. 覆盖多种情况：
   • Test 1-3: 小规模随机数据，便于手动验证。
   • Test 4: 边界 - 大量重复数字。
   • Test 5: 边界 - 不存在满足条件的数对 (答案为 0)。
   • Test 6: 边界 - 数组已排序（升序）。
   • Test 7: 边界 - 数组逆序。
   • Test 8: 较大规模数据，但数字范围较小（导致大量重复）。
   • Test 9-10: 满数据规模（$N=2 \times 10^5$），随机大数据，测试性能。

数据生成器代码 (generator.cpp)

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <random>
#include <chrono>

using namespace std;

// ==========================================
// 第一部分：标准解题逻辑 (用于生成 .out)
// ==========================================
long long solve_case(int n, long long c, vector<int>& a) {
    sort(a.begin(), a.end());
    long long count = 0;
    for (int i = 0; i < n; ++i) {
        long long target_a = (long long)a[i] + c;
        auto low = lower_bound(a.begin(), a.end(), target_a);
        auto high = upper_bound(a.begin(), a.end(), target_a);
        count += distance(low, high);
    }
    return count;
}

// ==========================================
// 第二部分：数据生成工具
// ==========================================

// 初始化高质量随机数引擎
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int random_int(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

// 生成单个测试点
void generate_data(int case_id, int n, long long max_c, int max_a, string type) {
    string in_file = to_string(case_id) + ".in";
    string out_file = to_string(case_id) + ".out";

    ofstream fout(in_file);

    long long c = random_int(1, max_c);
    fout << n << " " << c << endl;

    vector<int> a(n);
    if (type == "random") {
        for (int i = 0; i < n; ++i) {
            a[i] = random_int(1, max_a);
        }
    } else if (type == "duplicates") {
        // 生成大量重复数字
        int distinct_count = min(n, max(10, n / 10));
        vector<int> choices;
        for(int i=0; i<distinct_count; ++i) choices.push_back(random_int(1, max_a));
        for (int i = 0; i < n; ++i) {
            a[i] = choices[random_int(0, distinct_count - 1)];
        }
    } else if (type == "no_answer") {
        // 构造无解数据，让所有 a[j] - a[i] != c
        // 一个简单方法是让所有数都是奇数，而 c 是偶数
        c = random_int(1, max_c / 2) * 2;
        fout.seekp(0); // 回到文件开头重写
        fout << n << " " << c << endl;
        for (int i = 0; i < n; ++i) {
            a[i] = random_int(0, max_a / 2) * 2 + 1; // 生成奇数
        }
    } else if (type == "sorted") {
        for (int i = 0; i < n; ++i) {
            a[i] = random_int(1, max_a);
        }
        sort(a.begin(), a.end());
    } else if (type == "reversed") {
        for (int i = 0; i < n; ++i) {
            a[i] = random_int(1, max_a);
        }
        sort(a.rbegin(), a.rend());
    }

    // 写入 .in 文件
    for (int i = 0; i < n; ++i) {
        fout << a[i] << (i == n - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();

    // 计算标准答案并写入 .out 文件
    long long result = solve_case(n, c, a);
    ofstream f_ans(out_file);
    f_ans << result << endl;
    f_ans.close();

    cout << "Generated Case " << case_id << ": N=" << n 
         << " [" << type << "] -> Ans=" << result << endl;
}

int main() {
    // 题目约束 N <= 2e5, a < 2^30, C < 2^30
    // 2^30 约 1e9
    const int MAX_VAL = 1e9;

    // Test 1-3: 小数据
    generate_data(1, 10, 10, 20, "random");
    generate_data(2, 50, 20, 100, "random");
    generate_data(3, 100, 50, 200, "random");

    // Test 4: 边界 - 大量重复
    generate_data(4, 2000, 1000, 50, "duplicates");

    // Test 5: 边界 - 构造无解
    generate_data(5, 2000, 1000, 5000, "no_answer");
    
    // Test 6: 边界 - 预先排序
    generate_data(6, 5000, 2000, 10000, "sorted");

    // Test 7: 边界 - 逆序
    generate_data(7, 5000, 2000, 10000, "reversed");

    // Test 8: 较大 N，较小数值范围
    generate_data(8, 50000, 1000, 100, "random");

    // Test 9: 满数据
    generate_data(9, 200000, MAX_VAL, MAX_VAL, "random");

    // Test 10: 满数据，有大量重复
    generate_data(10, 200000, MAX_VAL, 1000, "duplicates");

    cout << "All 10 test cases generated successfully!" << endl;
    return 0;
}

如何使用

1. 将上面的代码保存为 generator.cpp。
2. 使用 C++11 或更高标准的编译器进行编译，例如： g++ generator.cpp -o generator -std=c++11
3. 运行生成的可执行文件： ./generator （在 Linux/macOS 上） generator.exe （在 Windows 上）
4. 程序运行后，当前目录下就会出现 1.in, 1.out, 2.in, 2.out, ..., 10.in, 10.out 这些文件。
5. 将这些文件上传到你的 OJ 系统即可。

你好！我是你的OI教练。

这道 P1102 A-B 数对是一道非常经典的题目，是检验你是否真正理解排序、二分查找和双指针这三大基础算法的试金石。

对于 $100\%$ 的数据 ($N \le 2 \times 10^5$)，一个 $O(N^2)$ 的暴力两层循环枚举是肯定会超时的。我们必须寻求更高效的 $O(N \log N)$ 或 $O(N)$ 的解法。

---

第一部分：思路提示与解法对比

解法一：排序 + 二分查找 ($O(N \log N)$)

1. 转化问题：我们要找的是 $A - B = C$，这等价于 $A = B + C$。
2. 核心思想：我们可以枚举每一个数作为 $B$，然后去序列中快速地寻找是否存在一个数 $A$ 等于 $B+C$。
3. 如何“快速寻找”？
   • 如果序列是无序的，我们每次寻找都得遍历一遍，总复杂度还是 $O(N^2)$。
   • 关键：如果我们先将整个序列排序，那么对于每一个 $B$，寻找 $A=B+C$ 的过程就可以用二分查找来完成，时间是 $O(\log N)$。
4. 处理重复数字：
   • 如果序列中有重复的数字，比如 1 1 2 3，C=1。
   • 当我枚举第一个 1 作为 $B$ 时，我需要在剩下的序列里找 $A=1+1=2$。二分查找能找到一个 2。
   • 但我怎么知道有多少个 2 呢？
   • 技巧：在 C++ STL 中，std::lower_bound 找的是第一个不小于目标值的迭代器，std::upper_bound 找的是第一个大于目标值的迭代器。
   • 那么，upper_bound(A) - lower_bound(A) 的结果，就是序列中等于 A 的元素个数！
5. 算法流程： a. 对整个数组 a 进行排序。 b. 初始化 count = 0。 c. 遍历排序后的数组 a，将每个元素 a[i] 当作 $B$。 d. 计算目标值 target_A = a[i] + C。 e. 在数组 a 中，用 lower_bound 和 upper_bound 查找 target_A 的出现次数，累加到 count 中。 f. 输出 count。

解法二：排序 + 双指针 ($O(N)$，排序后)

这是比二分查找更优的解法，总复杂度也是瓶颈在排序的 $O(N \log N)$。

1. 核心思想：同样先将数组排序。我们用两个指针 i 和 j，都从数组的左端开始。我们希望 a[j] - a[i] 恰好等于 C。

2. 指针移动策略：

   • 初始化 i = 0, j = 0。
   • 当 j < n 时，循环：
     • 计算差值 diff = a[j] - a[i]。
     • 如果 diff == C：说明我们找到了一个可能的数对。但是，可能存在多个 a[i] 和多个 a[j] 都是一样的。我们需要计算有多少个 a[i] 和多少个 a[j]。然后 count += (i的重复个数) * (j的重复个数)。之后移动 i 和 j 到下一个不同的数字。
     • 如果 diff < C：说明 a[j] 太小了，差值不够。我们需要增大 a[j]，所以 j++。
     • 如果 diff > C：说明 a[j] 太大了，差值过头了。我们需要增大 a[i]，所以 i++。

3. 处理重复数字 (更简洁的双指针):

   • 我们先不考虑一次性统计重复个数，而是让指针自然移动。
   • 初始化 i = 0, j = 1。
   • while (j < n):
     • 如果 a[j] - a[i] < C，j++
     • 如果 a[j] - a[i] > C，i++
     • 如果 a[j] - a[i] == C，此时我们找到了一个解。但是，可能有多个 a[j] 都是这个值。我们固定 i，让 j 继续向后走，直到 a[j] 不再是这个值，统计 j 走过的步数，累加到 ans。然后 i++。
   • 这种写法逻辑稍复杂。最简单的双指针是固定一个指针，移动另一个。

   推荐的双指针写法（固定 i，移动 j）：

   long long count = 0;
   int j = 0;
   for (int i = 0; i < n; i++) {
       // 对于每个 a[i] (作为 B)，我们希望找到 a[j] (作为 A)
       // a[j] = a[i] + C
       // j 只需要从 i 的右边开始找，并且 j 是单调不减的
       while (j < n && a[j] < a[i] + C) {
           j++;
       }
       
       // 此时 a[j] >= a[i] + C
       // 如果 a[j] == a[i] + C，说明找到了
       if (j < n && a[j] == a[i] + C) {
           // 需要统计有多少个 a[j]
           int temp_j = j;
           while (temp_j < n && a[temp_j] == a[i] + C) {
               count++;
               temp_j++;
           }
       }
   }
   

   这个版本是 $O(N^2)$ 的，因为 temp_j 可能会重复扫描。真正的 $O(N)$ 双指针需要更巧妙的设计。

   真正的 $O(N)$ 双指针 (处理重复数字)：

   long long ans = 0;
   for(int i = 0, j = 0; i < n; i++) {
       while(j < n && a[j] < a[i] + C) j++;
       // 此时 a[j] 是第一个 >= a[i] + C 的数
       
       // 我们要找的是 == a[i] + C 的数
       int j2 = j;
       while(j2 < n && a[j2] == a[i] + C) j2++;
       
       // 从 j 到 j2-1 都是满足条件的 A
       ans += j2 - j;
   }
   

   这个 j 指针只会向右移动，不会回溯，所以总复杂度是 $O(N)$。

---

第二部分：预备知识点总结

1. std::sort：必须掌握，是绝大多数高效算法的前提。
2. std::lower_bound 和 std::upper_bound：二分查找的利器，尤其擅长处理重复元素。
3. 双指针 (Two Pointers)：一种线性扫描的优化技巧，核心是利用单调性。
4. 数据类型：注意 N 最大 $2 \times 10^5$，数对的个数可能超过 int 的范围，要用 long long 存储结果。

---

第三部分：代码实现 (两种解法)

解法一：排序 + 二分查找

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 竞赛标准 IO 优化
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    long long c;
    std::cin >> n >> c;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 步骤1: 排序
    std::sort(a.begin(), a.end());

    long long count = 0;

    // 步骤2: 遍历每个元素作为 B
    for (int i = 0; i < n; ++i) {
        long long b = a[i];
        long long target_a = b + c;

        // 步骤3: 使用 lower_bound 和 upper_bound 查找 target_a 的个数
        // lower_bound 找到第一个 >= target_a 的位置
        auto low = std::lower_bound(a.begin(), a.end(), target_a);
        
        // upper_bound 找到第一个 > target_a 的位置
        auto high = std::upper_bound(a.begin(), a.end(), target_a);
        
        // 两者之差就是等于 target_a 的元素个数
        count += std::distance(low, high);
    }

    std::cout << count << std::endl;

    return 0;
}

解法二：排序 + 双指针 (最终优化版)

这个版本更难理解，但是效率更高。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    long long c;
    std::cin >> n >> c;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end());

    long long count = 0;
    
    // i, j 两个指针都从头开始
    // i 枚举 B, j 寻找 A
    for (int i = 0, j = 0; i < n; ++i) {
        // 移动 j，直到 a[j] 至少和 a[i] + C 一样大
        // 因为数组是排序的，j 只需要前进，不需要后退
        while (j < n && a[j] < a[i] + c) {
            j++;
        }
        
        // 此时，a[j] 是第一个 >= a[i] + c 的元素
        // 如果 a[j] 恰好等于 a[i] + c
        if (j < n && a[j] == a[i] + c) {
            // 那么，我们需要知道有多少个 a[i] 和多少个 a[j]
            // 更简单的思路是，我们只统计以当前 a[i] 开头的数对
            // 为了避免重复计算，我们可以先统计 a[i] 的数量
            int i_count = 1;
            while(i + 1 < n && a[i+1] == a[i]){
                i_count++;
                i++;
            }
            
            int j_start = j;
            while(j < n && a[j] == a[i] + c){
                j++;
            }
            int j_count = j - j_start;
            
            // 注意这里 j 指针已经移动到后面了，外层循环的 i 也会跳过重复
            count += (long long)i_count * j_count;
            // 因为 j 已经移动到不满足条件的位置，所以下一个 i 不需要从头找 j
            // 但 j 要回退一点，以便下一个不同的 i 可以从正确的位置开始
            j = j_start;
        }
    }
    // 上述写法比较复杂，我们还是用最经典的二分法思路
    // 真正的 O(N) 双指针不需要回退 j，只需要统计个数
    count = 0;
    for (int i = 0; i < n; ++i) {
        long long target_a = (long long)a[i] + c;
        // 对于每个a[i]，我们找有多少个 a[j] == target_a
        // 这不就是二分法的逻辑吗？
        // 所以本题最简洁的思路就是二分法
        auto low = std::lower_bound(a.begin() + i + 1, a.end(), target_a);
        auto high = std::upper_bound(a.begin() + i + 1, a.end(), target_a);
        count += std::distance(low, high);
    }


    std::cout << count << std::endl;

    return 0;
}

教练修正与最终推荐： 经过分析，对于这道题，“排序 + 二分查找” 的解法不仅在逻辑上最清晰、最不容易出错，而且代码也最简洁。lower_bound 和 upper_bound 内部实现就是二分，它们是解决这类“在有序序列中查找元素个数”问题的标准工具。双指针解法虽然理论上更快（排序后 $O(N)$ vs $O(N \log N)$），但处理重复元素时逻辑容易变得复杂，容易出错。

最终建议：在比赛中，对于这道题，毫不犹豫地使用排序+二分查找。总复杂度 $O(N \log N)$ 对于 $N=2 \times 10^5$ 来说绰绰有余。