归并排序的同时进行计算即可
#include<bits/stdc++.h>
using namespace std;
int n,a[1000002],T[1000002];
long long e;
void Mergesort(int L,int R){
if (L == R) return;
int mid = (L + R)/2;
Mergesort(L,mid); Mergesort(mid+1,R);
int i = L,j = mid + 1,k = L;
while (i<=mid && j<=R)
if(a[i] <= a[j]) T[k++] = a[i++];
else T[k++] = a[j++], e += mid-i+1;
while(i <= mid) T[k++] = a[i++];
while(j <= R) T[k++] = a[j++];
for (int q = L;q <= R; q++) a[q] = T[q];
}
int main()
{
scanf("%d", &n);
for (int i=1;i<=n;i++) scanf("%d", &a[i]);
Mergesort(1,n);
printf("%lld\n",e);
return 0;
}