题解

#include <bits/stdc++.h>
using namespace std;
int nums[500005] = {};
int tmps[500005];
long long ans = 0;
void merge(int l, int mid, int r) {
    int i=l;
    int j=mid+1;
    int k=l;
    while (i<=mid && j<=r) {
        if (nums[i]>nums[j]) {
            tmps[k++]=nums[j++];
            ans+=mid-i+1;
        }
        else tmps[k++]=nums[i++];
    }
    while (i<=mid)   tmps[k++]=nums[i++];
    while (j<=r)    tmps[k++]=nums[j++];
    for (i=l; i<=r; i++) {
        nums[i]=tmps[i];
    }
}
 
void mergeSort(int l, int r) {
    int mid;
    if (l < r) {
        mid = (l+r)/2;
        mergeSort(l, mid);
        mergeSort(mid+1, r);
        merge(l, mid, r);
    }
}
 
int main() {
    int n;
    cin >> n;
    int i;
    for (i=0; i<n; i++) cin >> nums[i];
    
    mergeSort(0, n-1);
    cout << ans << endl;
 
    return 0;
}