C++ 代码

#include <iostream>
using namespace std;

typedef long long LL; // 有可能有 n!个所以要大一点

const int N = 1e5+10;

int q[N], tmp[N];

LL merge_sort(int arr[], int l, int r) {
    if (l >= r) return 0;
    int mid = l+r >> 1;
    // 分别计算左右两边的逆序对
    LL res = merge_sort(arr, l, mid) + merge_sort(arr, mid+1, r);
    // 整体合并起来计算逆序对
    int i=l, j=mid+1, k=0;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++]; // 对于左边的arr[i]来说，没有逆序对，右边的所有元素都比它大(有序)
        else {
            // 对于 arr[j] 来说有逆序对，左边的所有元素都比它大(有序)
            res += mid - i + 1;
            tmp[k++] = arr[j++];
        }
    }

    while (j <= r) tmp[k++] = arr[j++];
    while (i <= mid) tmp[k++] = arr[i++];

    for (i=l,j=0; i<=r; i++, j++) arr[i] = tmp[j];

    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    cout << merge_sort(q, 0, n-1) << endl;
    return 0;
}