洛谷 P1102 A-B 数对

// P1102 的第 ① 版：两重循环，把每一对都试一遍
//
// ★ 它**不是废纸**：题面明写着「对于 75% 的数据，1 <= N <= 2000」——
//   N = 2000 时只有 200 万对，稳过。**考场上就是实打实的 75 分。**
//
// ⚠ 满数据 N = 2×10⁵ 时是 2×10¹⁰ 对，没有任何机会。
//
// ⚠ 就算是这一版，ans 也必须开 long long —— 溢出和快慢是两件独立的事，
//   一个「只能拿 75 分」的暴力，也可能在那 75% 里因为 int 溢出而变成 0 分。
//   （这道题的部分分数据 N <= 2000 ⇒ 最大 10⁶ 对，int 够用；但这一笔要算过才知道。）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, c;
    cin >> n >> c;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    long long ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (a[i] - a[j] == c) ans++;          // A = a[i], B = a[j]
    printf("%lld\n", ans);
    return 0;
}

// P1102 的第 ② 版：排序 + 二分（STL 的 lower_bound / upper_bound）
//
// 排好序之后，等于 a[i] + C 的那一块可以直接二分出来：
//
//     upper_bound(a, a[i] + C) - lower_bound(a, a[i] + C)
//
// O(N log N)，满数据 2×10⁵ 稳过。★ 它比双指针**更容易写对**：
// 不用想「指针要不要回退」，也不用想重复元素怎么数 —— 两个 STL 函数把边界替你管了。
//
// ⇒ 这一页想说的一句话：**双指针是把二分的 log 抹掉，不是「更正确」。**
//   考场上先写你最有把握的那个；这道题 N log N 和 N 都在时限里，二分完全够。
//
// ⚠ a[i] + C 会不会溢出 int：a_i、C 都小于 2³⁰ ⇒ 和最大 2 147 483 646，
//   而 int 上限 2 147 483 647 —— **只差 1**。见 p1102Count.cpp 那笔账。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, c;
    cin >> n >> c;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int want = a[i] + c;                       // B = a[i]，要找的 A
        ans += upper_bound(a.begin(), a.end(), want) - lower_bound(a.begin(), a.end(), want);
    }
    printf("%lld\n", ans);
    return 0;
}

// P1102 A-B 数对 —— 能 AC 的那一版：排序 + 双指针
//
// A − B = C 等价于 A = B + C。排好序之后，对每个 B = a[i]，
// 所有等于 a[i] + C 的元素在数组里是**连成一块**的，只要知道这块的两端就行。
//
// 两个指针都只往右走，一趟扫完：
//   j 停在第一个 a[j] − a[i] >= C 的位置        （这一块的左端）
//   k 停在第一个 a[k] − a[i] >  C 的位置        （这一块的右端 + 1）
//   这一块有 k − j 个 ⇒ ans += k − j
//
// ★ 为什么 j、k 不用回退：a[i] 单调不减 ⇒ a[i] + C 也单调不减 ⇒ 那一块只会往右挪。
//   这就是第 7 章第 3 步那条前提在「排好序的数组」上的样子。
//
// ★★ 用「减」不用「加」：这里写的是 `a[j] - a[i] < C`，不是 `a[j] < a[i] + C`。
//    两种写法在这道题上**都不会溢出**，但那是算出来的，不是碰运气 ——
//    a_i 和 C 都小于 2³⁰，和最大 2 147 483 646，而 int 上限 2 147 483 647。
//    ⇒ **富余量正好是 1。**（这笔账见 p1102Count.cpp，正文第 4 步专门讲了它。）
//
// ⚠ ans 必须是 long long：N = 2×10⁵ 时最大 10¹⁰（见 p1102Int.cpp）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, c;
    cin >> n >> c;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    long long ans = 0;
    int j = 0, k = 0;
    for (int i = 0; i < n; i++) {
        while (j < n && a[j] - a[i] < c) j++;       // 左端：第一个差 >= C
        while (k < n && a[k] - a[i] <= c) k++;      // 右端：第一个差 > C
        ans += k - j;
    }
    printf("%lld\n", ans);
    return 0;
}

// 演示错误写法：双指针只数了「第一个」匹配的元素 —— 重复元素全漏了
//
// 题面那句「**不同位置的数字一样的数对算不同的数对**」就是冲这个来的：
// a = [1, 1, 2, 3]、C = 1 时，A = 2 能配两个 B = 1，答案是 3 不是 2。
//
// ★ 这一版只找到那一块的左端就 ans++，等于把整块当成一个。
//   ⇒ 只要数据里有重复元素就会漏，**而重复元素在小值域的随机数据里满地都是**。
//   这也是第 7 章第 12 步刚踩过的坑（对撞指针数对时的「成块数」）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, c;
    cin >> n >> c;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    long long ans = 0;
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j < n && a[j] - a[i] < c) j++;
        if (j < n && a[j] - a[i] == c) ans++;       // ← 只数了一个，整块只算一次
    }
    printf("%lld\n", ans);
    return 0;
}

// P1102 的第 ③ 版：连排序都不用 —— 哈希表计数，O(N)
//
// 先把每个值出现了几次记进哈希表，然后对每个 B = a[i] 查一次 cnt[a[i] + C]。
//
// ★ 它和双指针一样是 O(N)，而且**根本不依赖顺序** ——
//   这说明这道题的「双指针」其实是可选的一条路，不是唯一解。
//
// ⚠ 但常数差得远：哈希表每次查询都要算哈希、可能碰撞、访问的内存到处乱跳；
//   双指针那一版从头到尾只是顺着数组走。正文第 7 步那张表量了这个差别。
//
// ⚠ unordered_map 在有心人构造的数据上会被卡成 O(N²)（哈希碰撞攻击），
//   洛谷这道题的数据没有这么干，但**知道有这回事**很重要。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, c;
    cin >> n >> c;
    vector<int> a(n);
    unordered_map<int, int> cnt;
    cnt.reserve(n * 2);
    for (int i = 0; i < n; i++) { cin >> a[i]; cnt[a[i]]++; }
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        auto it = cnt.find(a[i] + c);
        if (it != cnt.end()) ans += it->second;
    }
    printf("%lld\n", ans);
    return 0;
}

// 数据生成器（P1102 对拍用）：`./p1102Gen <seed> [level]`
//
//   level 0（默认）n <= 12、a_i <= 20、C <= 10  —— **值域故意压得很小，重复元素满地都是**
//   level 1        n <= 200、a_i <= 30、C <= 15 —— 重复更密，答案更大
//   level 2        **顶格值域**：C 贴着 2³⁰，值只取 {0, 1, C-1, C, 2³⁰-1}
//
// ★ level 0 / 1 是给 p1102One（漏掉重复元素）准备的：
//   值域压小 ⇒ 重复必然出现 ⇒ 那个 bug 每一轮都露头。
//   （第 6 章 P1719 那条：**对拍的小数据不是「凑合」，小本身就是覆盖能力。**）
//
// ★★ level 2 是给「a_i + C 会不会溢出」那笔账准备的：
//   它把 a_i + C 顶到 2 147 483 646 —— 离 int 的上限只差 1。
//   这一档三百轮全一致，就是那笔账**被跑过一遍**的证据。
//
// ⚠ 这个生成器**造不出**答案溢出的数据：那需要 N >= 92 682（见 p1102Count.cpp）。
//   ⇒ p1102Int.cpp 那个 bug 在这里是「算术上不可能」抓到的，不是「概率低」。

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

static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    unsigned seed = (argc > 1) ? (unsigned)atoi(argv[1]) : 1;
    int level = (argc > 2) ? atoi(argv[2]) : 0;
    rng.seed(seed);

    if (level == 2) {
        int n = ri(2, 12);
        int c = (1 << 30) - ri(1, 10);
        printf("%d %d\n", n, c);
        int pool[5] = {0, 1, c - 1, c, (1 << 30) - 1};
        for (int i = 0; i < n; i++) printf("%d%c", pool[ri(0, 4)], i == n - 1 ? '\n' : ' ');
        return 0;
    }
    int n = (level == 1) ? ri(2, 200) : ri(1, 12);
    int hi = (level == 1) ? 30 : 20;
    int c = (level == 1) ? ri(1, 15) : ri(1, 10);
    printf("%d %d\n", n, c);
    for (int i = 0; i < n; i++) printf("%d%c", ri(0, hi), i == n - 1 ? '\n' : ' ');
    return 0;
}

// 大数据生成器（P1102 计时 / 溢出用）：`./p1102GenBig <n> [level] [C]`
//
//   level 0（默认）**顶格形状**：一半是 x、一半是 x + C ⇒ 答案 = floor(n/2) × ceil(n/2)，
//                  这是这道题答案能到的最大值，也是 int 唯一会翻车的形状
//   level 1        随机：a_i 在整个 [0, 2³⁰) 上均匀取 ⇒ 答案几乎必然是 0
//
// ★ 两个档位的对比就是「顶格 ≠ 随机」：同样是 n = 2×10⁵，
//   档位 0 的答案是 10¹⁰，档位 1 的答案大概率是 0 ——
//   **拿档位 1 去测「答案会不会溢出」，测一辈子也测不出来。**

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

static mt19937 rng;

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 200000;
    int level = (argc > 2) ? atoi(argv[2]) : 0;
    int c = (argc > 3) ? atoi(argv[3]) : 1;
    rng.seed(12345);
    printf("%d %d\n", n, c);
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        v[i] = (level == 0) ? ((i < n / 2) ? 1000 : 1000 + c) : (int)(rng() & ((1u << 30) - 1));
    shuffle(v.begin(), v.end(), rng);                 // 打乱：别让排序捡到「已经有序」的便宜
    for (int i = 0; i < n; i++) printf("%d%c", v[i], i == n - 1 ? '\n' : ' ');
    return 0;
}

// 三笔账 + 一把秒表
//
// 用法：./p1102Count <N>        人话版
//       ./p1102Count <N> csv    只打 `键,值`，给 check:viz 用
//
// ① 尺子：暴力要试 N² 对；排序 + 双指针只扫 3N 次（一次排序 + 两个指针各走一趟）。
// ② 溢出账之一（**答案**）：一半是 x、一半是 x + C 时答案最大，
//    等于 floor(N/2) × ceil(N/2)。它从哪个 N 开始越过 int？—— 这是**算出来**的一条线。
// ③ 溢出账之二（**中间量**）：a_i < 2³⁰、C < 2³⁰ ⇒ a_i + C 最大 2 147 483 646，
//    而 int 上限 2 147 483 647。★★ **富余量正好是 1。**
//
// ⚠ ③ 这一笔是这道题最险的地方：它**不溢出**，但只要题面把 a_i 的上界写成 2³⁰（含）
//    而不是「小于 2³⁰」，`a[i] + C` 就当场翻车。⇒ 「算过了确认不用」和「没算过」是两回事。

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

static double now_ms() {
    timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec * 1000.0 + t.tv_nsec / 1e6;
}

int main(int argc, char** argv) {
    long long N = (argc > 1) ? atoll(argv[1]) : 200000;
    bool csv = (argc > 2 && string(argv[2]) == "csv");

    long long intMax = 2147483647LL;
    long long brute = N * N;
    long long two = 3 * N;

    long long ansMax = (N / 2) * (N - N / 2);            // 一半 x、一半 x+C
    long long lineN = 0;                                  // 第一个让 ansMax 越过 int 的 N
    for (long long k = 2; ; k++) {
        if ((k / 2) * (k - k / 2) > intMax) { lineN = k; break; }
    }
    long long belowMax = ((lineN - 1) / 2) * ((lineN - 1) - (lineN - 1) / 2);
    long long lineMax = (lineN / 2) * (lineN - lineN / 2);

    long long aMax = (1LL << 30) - 1;                     // 题面：a_i < 2^30
    long long cMax = (1LL << 30) - 1;                     // 题面：C < 2^30
    long long sumMax = aMax + cMax;
    long long margin = intMax - sumMax;

    /* 秒表：顶格形状（一半 x、一半 x+C）上三种能过的写法 */
    int n = (int)N, c = 1;
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = (i < n / 2) ? 1000 : 1000 + c;

    vector<int> b = a;
    double t0 = now_ms();
    sort(b.begin(), b.end());
    long long ansTwo = 0;
    { int j = 0, k = 0;
      for (int i = 0; i < n; i++) {
          while (j < n && b[j] - b[i] < c) j++;
          while (k < n && b[k] - b[i] <= c) k++;
          ansTwo += k - j;
      } }
    double tTwo = now_ms() - t0;

    b = a;
    t0 = now_ms();
    sort(b.begin(), b.end());
    long long ansBin = 0;
    for (int i = 0; i < n; i++) {
        int want = b[i] + c;
        ansBin += upper_bound(b.begin(), b.end(), want) - lower_bound(b.begin(), b.end(), want);
    }
    double tBin = now_ms() - t0;

    t0 = now_ms();
    unordered_map<int, int> cnt;
    cnt.reserve(n * 2);
    for (int i = 0; i < n; i++) cnt[a[i]]++;
    long long ansMap = 0;
    for (int i = 0; i < n; i++) {
        auto it = cnt.find(a[i] + c);
        if (it != cnt.end()) ansMap += it->second;
    }
    double tMap = now_ms() - t0;

    if (csv) {
        printf("N,%lld\nbrute,%lld\ntwo,%lld\nratio,%lld\n"
               "ansMax,%lld\nansFitsInt,%d\nlineN,%lld\nbelowMax,%lld\nlineMax,%lld\n"
               "aMax,%lld\ncMax,%lld\nsumMax,%lld\nintMax,%lld\nmargin,%lld\n"
               "sameAns,%d\n",
               N, brute, two, brute / two,
               ansMax, ansMax <= intMax ? 1 : 0, lineN, belowMax, lineMax,
               aMax, cMax, sumMax, intMax, margin,
               (ansTwo == ansBin && ansTwo == ansMap) ? 1 : 0);
    } else {
        printf("N = %lld\n\n", N);
        printf("(1) 两重循环      %14lld 次\n", brute);
        printf("(2) 排序 + 双指针 %14lld 次   => 差 %lld 倍\n\n", two, brute / two);
        printf("答案的上界（一半 x、一半 x+C）：%lld  => int %s\n",
               ansMax, ansMax <= intMax ? "够" : "不够");
        printf("  越线的 N 是 %lld：N = %lld 时最大 %lld（不到），N = %lld 时 %lld（越过）\n\n",
               lineN, lineN - 1, belowMax, lineN, lineMax);
        printf("中间量 a_i + C 的上界：%lld + %lld = %lld\n", aMax, cMax, sumMax);
        printf("int 的上限                      %lld  => 富余量 %lld\n\n", intMax, margin);
        printf("顶格形状上的秒表（答案 %lld）：\n", ansTwo);
        printf("  排序 + 双指针   %8.1f ms\n", tTwo);
        printf("  排序 + 二分     %8.1f ms\n", tBin);
        printf("  哈希表计数      %8.1f ms\n", tMap);
    }
    return 0;
}