C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e8 + 10;
int n;
int q[maxn], tmp[maxn];

LL merge_sort(int l, int r)
{
    if(l<=r) return ;
    int mid = l+r>>1;
    LL res =merge_sort(l,mid)+merge_sort(mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    if(q[i]<=q[j]) tmp[k++]=q[i++];
    else 
    {
        tmp[k++]=q[j++];
        res+= mid-i+1;
    }  
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];
    for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];   
    return res;

}

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