题目

题意

给定一个长度为$n$的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第$i$个和第$j$个元素，如果满足$i\lt j$且$a[i]>a[j]$，则其为一个逆序对；否则不是。

输入格式

第一行包含整数$n$，表示数列的长度。
第二行包含$n$个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

$1\leqslant n\leqslant 100000$，数列中的元素的取值范围$[1,10^9]$。

时空限制

1s / 64MB

样例

输入样例

6
2 3 4 5 6 1

输出样例

5

解答

穷举（无法通过OJ）

思路

• 穷举所有$i \lt j$的情况，判断是否满足前一个元素大于后一个元素
• 时间复杂度为$O(n^2)$

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5;
int a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    int res = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] > a[j]) res++;

    printf("%d\n", res);

    return 0;
}

[!warning]
虽然这个算法是正确的，但时间复杂度过高，无法通过AcWing的OJ

归并排序

思路

可以采用分治策略。对于任意有序对$<a_i, a_j>$（$i \lt j$），它们可能的位置有如下情况
1. 都在左半边
2. 都在右半边
3. $a_i$在左半边，$a_j$在右半边
第1类和第2类问题为重复子问题，可递归处理，而第3类问题需要特殊处理。

当左半段和右半段都是无序序列时，第3类问题只能通过穷举来得到逆序对的个数，此时得到递推方程$T(n)=2T(\frac{n}{2}) + O(n^2)$。根据主定理知$T(n)=O(n^2)$，此时分治算法没有降低时间复杂度。

当左半段和右半段都是有序序列时，第3类问题有更快的求解方法。
不妨假设左半段的范围为$left$~$mid$，右半段的范围为$mid + 1$~$right$，它们都已经升序排列。指针$i$和$j$分别遍左半段和右半段。
当$a_i \gt a_j$时，左半段位于$i$~$mid$的元素都大于$a_j$，因此可得到$mid - i + 1$个逆序对：$<a_i, a_j>$、$<a_{i + 1}, a_j>$、$\cdots$、$<a_{mid}, a_j>$。
当两个指针遍历完左半段和右半段后，就能只以$O(n)$的代价找到第三类问题中逆序对的数量，大大降低时间复杂度。

可以发现，这个过程正是归并排序的合并过程。因此我们可以在调用归并排序时，顺便统计逆序对的数量，就能得到整个数组的逆序对的数量，时间复杂度由穷举法$O(n^2)$降为$O(n \log n)$。

由于逆序对的数量可能会超过$(10^5)^2=10^{10} \gt 10^9$，因此需要用int64_t来存储结果。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5;
int a[N], tmp[N];
int64_t res = 0;

void merge_sort(int a[], int left, int right) {
    if (left >= right) return;

    int mid = left + right >> 1;
    merge_sort(a, left, mid);
    merge_sort(a, mid + 1, right);

    int i = left, j = mid + 1, k = left;
    while(i <= mid && j <= right)
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            res += mid - i + 1;  // 位于i~mid的元素都能与a[j]组成逆序对
        }
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= right) tmp[k++] = a[j++];

    for (k = left; k <= right; k++) a[k] = tmp[k];  // 复制回数组
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    merge_sort(a, 0, n - 1);

    printf("%lld\n", res);

    return 0;
}

总结

本题难点在于如何把问题联系到归并排序上，进而更能深刻理解归并排序的分治思想。