P4669 逆序对（基础）

解题思路

第一步，理解什么是逆序对。 一对数 nums[i] 和 nums[j]，如果 i < j（左边在前）但 nums[i] > nums[j]（左边的反而更大），就是一对逆序对，也就是"前面的数比后面的数大"。比如序列 3 1 2 里，3>1、3>2，一共 2 对。注意要求是"大于"而不是"大于等于"，所以相等的两个数不算逆序对。

第二步，想一个聪明的统计办法。 直接两两比较要 O(n²)，n 很大时会超时。我们借用归并排序：归并排序要把两个已经各自有序的区间合并成一个，合并的时候正好可以顺手数出逆序对。

第三步，合并时统计。 合并左区间 l~mid 和右区间 mid+1~r 时，两个区间内部都是升序的。用 i 指向左边的当前数、j 指向右边的当前数：如果 nums[i] <= nums[j]，说明 nums[i] 不大于右边的数，不是逆序对，把它放进结果数组；如果 nums[i] > nums[j]，说明右区间的 nums[j] 比左区间从 i 到 mid 的所有数都小，这些数全都和 nums[j] 构成逆序对，一共 mid-i+1 对，全部加进答案 ans。

第四步，收尾。 把两边剩下的数依次放进结果数组，再把结果复制回原数组。每个逆序对恰好在某一次合并中被统计一次，不会漏也不会重。

想一想生活里的例子。 老师按学号点名，如果发现"后面的同学比前面的同学高"，就算一对"高低颠倒"。

边界情况： n 最多 2500，其实两重循环也能过，但归并排序 O(n log n) 更通用；数字最大 1e9 用 int 存得下，但逆序对最多约 n(n-1)/2 对，答案要用 long long 存。

参考代码

// P4669 逆序对：归并排序过程中统计 nums[i] > nums[j] 且 i < j 的对数
#include <iostream>
int nums[1000005], temp[1000005];
long long ans = 0;

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 (nums[i] <= nums[j]) temp[k++] = nums[i++];
        else {
            ans += (long long)(mid - i + 1);   // 左边剩余的数都比 nums[j] 大，全是逆序对
            temp[k++] = nums[j++];
        }
    }
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= r) temp[k++] = nums[j++];
    for (int p = l; p <= r; p++) nums[p] = temp[p];
}

int main() {
    int n;
    std::cin >> n;
    for (int i = 0; i < n; i++) std::cin >> nums[i];
    mergeSort(0, n - 1);
    std::cout << ans << "\n";
    return 0;
}

复杂度分析

归并排序本身是 O(n log n)，合并过程中顺手统计逆序对，不增加额外的时间复杂度。n 最大 2500，即使 n 更大一些也能轻松处理。空间上需要两个数组 nums 和 temp，O(n)。答案可能很大，用 long long 保存，避免 int 溢出。这是"排序算法边排序边做事"的经典应用。