C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;
int p[N];
int tmp[N];


long long merge_sort(int x[], int l, int r, int t[]) {
    if (l >= r) {
        return 0;
    }
    int mid = (l + r) >> 1;
    long long  left_count = merge_sort(x, l, mid, t);
    long long  right_count = merge_sort(x, mid + 1, r, t);

    int i = l, j = mid + 1;
    int k = 0;
    long long  result  = left_count + right_count;
    while(i <= mid && j <= r) {
        if (x[i] <= x[j]) {
            t[k ++] = x[i ++];
        } else {
            result += (mid - i + 1);
            t[k ++] = x[j ++];
        }
    }

    while(i <= mid) {
        t[k ++] = x[i ++];
    }
    while(j <= r) {
         t[k ++] = x[j ++];
    }
    k = 0;
    for (int i = l; i <= r; ++i) {
        x[i] = t[k++];
    }
    return result;
}


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

    long long x = merge_sort(p, 0, n - 1, tmp);
    printf("%lu", x);

    return 0;
}