给我简单讲解“归并排序求逆序对”

归并排序求逆序对是分治思想（Divide and Conquer）最经典的实战应用，也是 CSP-J/S、NOIP 初赛代码填空和复赛算法题的必考模板。

一、什么是逆序对？

在数组 $A$ 中，如果存在一对下标满足：

则称 $(A[i], A[j])$ 是一个逆序对。

• 物理本质：一个序列的逆序对数量，等于冒泡排序将其排成升序所需的相邻元素交换总次数。
• 暴力做法：双重循环枚举 $i, j$，耗时 $O(n^2)$，当 $n=10^5$ 时直接超时（TLE）。
• 归并排序法：在排序合并（Merge）的同时顺手统计，时间复杂度优化到 $O(n \log n)$。

二、核心计算原理（为什么归并可以顺手求？）

在归并排序的“分治”过程中，任意一个逆序对 $(A[i], A[j])$ 只可能落在三种情况中：

1. 完全在左半区间：递归调用左半边解决；
2. 完全在右半区间：递归调用右半边解决；
3. 横跨左右区间（$i$ 在左，$j$ 在右）：在双指针 merge 时一次性批量计算！

跨区间计算的关键逻辑：

假设左半区 [L, mid] 和右半区 [mid+1, R] 都已经排好升序：

• 设指针 $i$ 遍历左区，指针 $j$ 遍历右区；

• 若 $A[i] \le A[j]$：正常取出 $A[i]$，不构成逆序对，$i{++}$；

• 若 $A[i] > A[j]$： 因为左半区本身是有序的，既然 $A[i] > A[j]$，那么左区中从 $i$ 到 $mid$ 的所有元素（$A[i], A[i+1], \dots, A[mid]$）都必然大于 $A[j]$！

  $$\text{本步新增逆序对数} = \mathbf{mid - i + 1}$$

三、手算演练（一图看懂）

合并以下两个已经排好序的子区间（mid = 2）：

• 左半区：[ 2, 5, 8 ]（下标 $i$ 从 0 到 2）
• 右半区：[ 3, 4, 7 ]（下标 $j$ 从 3 到 5）

第1步: A[i]=2 <= A[j]=3  -> 取出 2, 逆序对 +0
第2步: A[i]=5 >  A[j]=3  -> 取出 3, 逆序对 += (mid - i + 1) = (2 - 1 + 1) = 2对!
                           (即 (5,3) 和 (8,3) 这一对批处理全数拿到)
第3步: A[i]=5 >  A[j]=4  -> 取出 4, 逆序对 += (2 - 1 + 1) = 2对!
                           (即 (5,4) 和 (8,4))
第4步: A[i]=5 <= A[j]=7  -> 取出 5, 逆序对 +0
第5步: A[i]=8 >  A[j]=7  -> 取出 7, 逆序对 += (2 - 2 + 1) = 1对!
                           (即 (8,7))
第6步: 左边剩余 8 全部放入。

总计产生跨区间逆序对 = 0 + 2 + 2 + 0 + 1 = 5 对。

四、高频踩坑点（考场失分雷区）

1. 必须开 long long（致命易错）：
   • 当数组长度 $n = 10^5$ 时，逆序对数量最多可达：$$\frac{n(n-1)}{2} \approx \frac{10^{10}}{2} = 5 \times 10^9 $$
   • 32 位整型 int 上限约为 $2.14 \times 10^9$，必定爆 int！统计变量 ans 必须声明为 long long。
2. 比较条件必须是 $A[i] \le A[j]$（必须带等号）：
   • 逆序对要求严格大于（$A[i] > A[j]$）。
   • 若两数相等（$A[i] == A[j]$），不构成逆序对，必须优先放左区元素（$i{++}$），否则会误算逆序对且破坏算法稳定性。

五、标准 C++ 模板（背诵级精简代码）

#include <iostream>
using namespace std;

const int MAXN = 100005;
int a[MAXN], temp[MAXN];
long long ans = 0; // 必须 long long

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); // 递归求右半区

    // 双指针合并与统计
    int i = L, j = mid + 1, k = L;
    while (i <= mid && j <= R) {
        if (a[i] <= a[j]) { // 相等时优先放左边
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
            ans += (mid - i + 1); // 核心统计语句！
        }
    }
    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() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    merge_sort(1, n);
    cout << ans << endl;
    return 0;
}