归并排序求逆序对

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 5e5 + 7;
int n; ll cnt;
int a[maxn], b[maxn];
void merg(int L,int M,int R)
{
    int i = L, j = M, k = L;
    while(i < M && j < R)
    {
        if(a[i] > a[j])
        {
            b[k++] = a[j++];
            cnt += M - i;
        }
        else b[k++] = a[i++];
    }
    while(i < M) b[k++] = a[i++];
    while(j < R) b[k++] = a[j++];
    for(i = L; i < R; i++) a[i] = b[i];
}
void MergeSort(int L, int R)
{
    if(L + 1 >= R) return ;
    int M = (L + R) >> 1;
    MergeSort(L, M);
    MergeSort(M, R);
    merg(L, M, R);
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        scanf("%d",&a[i]);
    MergeSort(0, n);
    cout << cnt << endl;
    return 0;
}