题解 100% AC

#include <bits/stdc++.h>
using namespace std;
int a[5000010],c[5000010],n,k;
long long ncnt;
void mergesort(int l,int r){
    if(l==r) return;
    int mid=(l+r)/2;
    mergesort(l,mid);
    mergesort(mid+1,r);
    int l1=l,r1=mid,l2=mid+1,r2=r,cnt=l1;
    while(l1<=r1&&l2<=r2){
        if(a[l1]<=a[l2])c[cnt++]=a[l1++];
        else{
            c[cnt++]=a[l2++];
            ncnt+=(r1-l1+1);
        }
    }
    while(l1<=r1) c[cnt++]=a[l1++];
    while(l2<=r2) c[cnt++]=a[l2++];
    for(int i=l;i<=r;i++) a[i]=c[i];
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    mergesort(1,n);
    cout<<ncnt;
    return 0;
}