你好！我是你的OI教练。今天我们来讲解 GESP 2023年9月六级的真题《小杨的握手问题》。

这道题其实是经典算法**“求逆序对”的孪生兄弟**。如果你熟悉“归并排序求逆序对”的模板，这道题对你来说就是送分题。

我们先在草稿纸上把逻辑理顺。

1. 读题关键词与转化

1. 规则：“每位同学进入教室时，需要和 已经在教室内 且 学号小于自己 的同学握手。”
   • 翻译成数学语言：对于数组中的每一个数 $A[i]$（新进来的），我们要统计在它左边（$j < i$）有多少个 $A[j]$ 满足 $A[j] < A[i]$。
2. 目标：求所有这些统计量的总和。
   • 也就是求满足 $j < i$ 且 $A[j] < A[i]$ 的数对 $(j, i)$ 的数量。
   • 这种数对通常叫“顺序对”（与“逆序对”相反）。
3. 数据范围：$N \le 3 \times 10^5$。
   • 暴力解法（双重循环）是 $O(N^2)$，计算量约为 $9 \times 10^{10}$，绝对超时。
   • 我们需要 $O(N \log N)$ 的解法。
4. 提示：“使用归并排序进行降序排序”。

2. 核心思路：归并排序的“魔法”

我们知道，**归并排序（Merge Sort）**的过程是将两个已经有序的子数组合并成一个大的有序数组。

假设我们要合并两个区间：Left 区间（下标较小，代表已经在教室里的人）和 Right 区间（下标较大，代表后进来的人）。

题目提示我们要降序排序（从大到小）。假设 Left 和 Right 内部都已经是从大到小排好序的：

• Left: [8, 5, 2]
• Right: [9, 6, 1]

我们设置两个指针，i 指向 Left 开头，j 指向 Right 开头。

比较 $Left[i]$ 和 $Right[j]$：

1. 情况一：$Left[i] > Right[j]$

   • 例如 8 和 6。
   • 这表示“先进来的人”学号比“后进来的人”大。
   • 不握手。
   • 为了维持降序，把大的 8 放入临时数组，i 后移。

2. 情况二：$Left[i] < Right[j]$

   • 例如 5 和 6。
   • 注意！Left[i] 是 5，Right[j] 是 6。
   • 这意味着：后进来的 6 比 先进来的 5 大 $\rightarrow$ 握手！
   • 关键推理：
     • 因为 Left 是从大到小排好序的。
     • 既然 6 比 5 大，那么 6 一定比 5 后面的所有数（比如 2）都大。
     • 所以，Right[j] (也就是 6) 会和 Left[i] 以及 Left 中剩余的所有人握手。
     • 握手次数增加： (Left的长度 - i) 或 (mid - i + 1)。
   • 把较大的 6 放入临时数组，j 后移。

通过这种方式，我们在排序的同时，一次性计算出了一批握手次数，将复杂度降到了 $O(N \log N)$。

3. 标准代码 (NOIP C++14)

/**
 * 题目：B3874 [GESP202309 六级] 小杨的握手问题
 * 考点：归并排序、分治思想、求顺序对
 * 时间复杂度：O(N log N)
 */

#include <iostream>
#include <vector>

using namespace std;

// 关键点1：结果可能很大。N=3*10^5，总对数接近 N^2/2 ≈ 4.5*10^10。
// int 最大 2*10^9，存不下，必须用 long long。
long long ans = 0;
const int MAXN = 300005;
int a[MAXN];      // 原数组
int temp[MAXN];   // 归并排序用的临时数组

// 归并排序函数 (降序)
void merge_sort(int l, int r) {
    if (l >= r) return; // 只有一个元素或区间非法，无需排序

    int mid = (l + r) / 2;
    merge_sort(l, mid);      // 递归处理左边
    merge_sort(mid + 1, r);  // 递归处理右边

    // 合并两个有序子数组 [l, mid] 和 [mid+1, r]
    int i = l;          // 左半边指针
    int j = mid + 1;    // 右半边指针
    int k = l;          // 临时数组指针

    while (i <= mid && j <= r) {
        // 我们要降序排列 (从大到小)
        
        if (a[i] > a[j]) {
            // 左边的比右边的大
            // 这是正常情况（逆序），不产生握手（因为题目要求 小的在左边 才能握手）
            temp[k++] = a[i++];
        } 
        else {
            // a[i] < a[j]
            // 左边(先入场) < 右边(后入场) -> 满足握手条件！
            // 因为左边是降序的，如果 a[j] 比 a[i] 大，
            // 那么 a[j] 一定比 a[i] 后面的所有元素（a[i+1]...a[mid]）都大。
            // 所以 a[j] 会和 a[i] 到 a[mid] 的所有人都握手。
            
            ans += (long long)(mid - i + 1); // 累加握手次数
            
            // 将较大的数放入临时数组（因为是降序排序）
            temp[k++] = a[j++];
        }
    }

    // 处理剩余元素
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];

    // 将排序好的部分拷回原数组
    for (int p = l; p <= r; p++) {
        a[p] = temp[p];
    }
}

int main() {
    // IO 优化
    ios::sync_with_stdio(false);
    cin.tie(0);

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

        merge_sort(0, n - 1);

        cout << ans << endl;
    }

    return 0;
}

4. 数据生成器 (1.in - 10.in)

为了充分测试，我们需要生成不同规模、不同特征的数据：

• 小数据 ($N \le 100$)
• 大数据 ($N \approx 3 \times 10^5$)
• 完全升序（握手次数最多）
• 完全降序（握手次数为 0）
• 随机数据

/**
 * B3874 数据生成器
 * 生成 1.in/1.out ~ 10.in/10.out
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

// ==========================================
// Part 1: 标准题解逻辑 (用于生成 .out)
// ==========================================
long long solve_ans = 0;
vector<int> solve_temp;

void solve_merge(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    solve_merge(arr, l, mid);
    solve_merge(arr, mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (arr[i] > arr[j]) {
            solve_temp[k++] = arr[i++];
        } else {
            solve_ans += (mid - i + 1);
            solve_temp[k++] = arr[j++];
        }
    }
    while (i <= mid) solve_temp[k++] = arr[i++];
    while (j <= r) solve_temp[k++] = arr[j++];
    for (int p = l; p <= r; p++) arr[p] = solve_temp[p];
}

long long get_answer(int n, vector<int> arr) {
    solve_ans = 0;
    solve_temp.assign(n, 0);
    solve_merge(arr, 0, n - 1);
    return solve_ans;
}

// ==========================================
// Part 2: 数据构造逻辑
// ==========================================

// 生成随机排列 (0 到 n-1)
vector<int> generate_permutation(int n, int type) {
    vector<int> v(n);
    for (int i = 0; i < n; i++) v[i] = i;
    
    if (type == 0) {
        // 完全随机
        random_shuffle(v.begin(), v.end());
    } else if (type == 1) {
        // 完全升序 (握手最多)
        // do nothing
    } else if (type == 2) {
        // 完全降序 (握手为0)
        reverse(v.begin(), v.end());
    } else if (type == 3) {
        // 局部有序
        random_shuffle(v.begin(), v.end());
        sort(v.begin(), v.begin() + n/2);
    }
    return v;
}

void makeData(int fileId) {
    string inName = to_string(fileId) + ".in";
    string outName = to_string(fileId) + ".out";
    ofstream fin(inName);
    ofstream fout(outName);

    int N;
    int type = 0; // 0:random, 1:asc, 2:desc

    // 梯度设置
    if (fileId <= 3) {
        N = rand() % 100 + 5; // 小数据
        if (fileId == 2) type = 1;
        if (fileId == 3) type = 2;
    } else if (fileId <= 6) {
        N = rand() % 10000 + 1000; // 中等数据
    } else {
        N = 300000; // 极限数据
        if (fileId == 9) type = 1; // 极限升序
        if (fileId == 10) type = 2; // 极限降序
    }

    vector<int> arr = generate_permutation(N, type);

    fin << N << endl;
    for (int i = 0; i < N; i++) {
        fin << arr[i] << (i == N - 1 ? "" : " ");
    }
    fin << endl;

    // 计算答案
    fout << get_answer(N, arr) << endl;

    fin.close();
    fout.close();
    cout << "Generated Case " << fileId << " (N=" << N << ")" << endl;
}

int main() {
    srand(time(0));
    for (int i = 1; i <= 10; i++) {
        makeData(i);
    }
    cout << "All data generated." << endl;
    return 0;
}

教练总结

1. 思维转换：看到“求前面有多少个比自己小/大”的问题，条件反射就要想到归并排序或树状数组。这是竞赛中的基本套路。
2. 符号方向：在写归并排序时，> 还是 <，ans 加的是 mid-i+1 还是 j-mid，一定要在草稿纸上模拟一遍（比如用 [5, 2] 和 [6, 1] 这种简单的例子），不要死记硬背。
3. 数据类型：再次强调 long long！只要是 $N^2$ 级别的计数，int 必爆。