P4651 逆序对比赛（提高）

解题思路

第一步，理解"逆序对"的定义。 在序列中找两个位置 i<j，如果 a[i]>a[j]，这一对数就叫一个逆序对。注意序列里可能有重复数字，题目要求的是严格大于，也就是两个相等的数不能算作逆序对。比如序列 3,1,2 中，3 和 1、3 和 2 都是逆序对，一共 2 对。

第二步，想想暴力做法为什么不行。 两重循环枚举所有 i 和 j 自然能数出答案，但如果 n 有几十万甚至上百万，O(n²) 的暴力会完全超时。我们必须想一个更快的办法。

第三步，请出"归并排序"这位得力助手。 归并排序把序列分成左右两半，各自排好序后再合并。合并时比较左边指针指向的数 a[i] 和右边指针指向的数 a[j]：如果 a[i]<=a[j]，说明 a[i] 不会和 a[j] 形成逆序对，直接把 a[i] 放进临时数组；如果 a[i]>a[j]，因为左边已经排好序，a[i] 是左边这一段里最小的，所以左边从 a[i] 到 a[mid] 这一整段都比 a[j] 大，它们全部和 a[j] 构成逆序对，一次加上 mid-i+1 个。这样每一对逆序对恰好被统计一次，既不会重复也不会遗漏。

第四步，注意两个容易踩的坑。 数据里每个数最大 10 亿，用 int 就存得下；但逆序对的数量最多有 n(n-1)/2 对，可能非常大，必须用 long long 来存答案。只要记住这两点，代码就不容易写错。

第五步，换个角度加深理解。 把序列排成从小到大的顺序，逆序对的个数其实就是"排序过程中需要交换位置的两个数组成的对数"。每一次从右边取出较小的数 a[j] 时，左边还没取走的数都比它大，它们本应排在 a[j] 前面，现在却排在后面，每一对都是一次"位置翻转"。用 answer 把这些数量累加起来，就是最终答案。

参考代码

// P4651 逆序对比赛：用归并排序统计满足 a[i]>a[j] 且 i<j 的逆序对个数
#include <iostream>
using namespace std;

int num[1000005], temp[1000005];
long long answer;

// 归并排序，排序过程中顺便统计逆序对
void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (num[i] <= num[j]) {
            temp[k++] = num[i++];
        } else {
            // num[i]~num[mid] 都比 num[j] 大，都构成逆序对
            answer += mid - i + 1;
            temp[k++] = num[j++];
        }
    }
    while (i <= mid) temp[k++] = num[i++];
    while (j <= r) temp[k++] = num[j++];
    for (i = l; i <= r; i++) num[i] = temp[i];
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> num[i];
    answer = 0;
    mergeSort(0, n - 1);
    cout << answer << endl;
    return 0;
}

复杂度分析

归并排序的时间复杂度是 O(n log n)：每一层合并要遍历全部的 n 个元素，一共有 log2(n) 层。空间复杂度是 O(n)，因为需要一个和原数组等长的临时数组 temp。n 即使取到 100 万，log2(100万)≈20，大约 2000 万次操作，也能在一秒内完成。