归并排序

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1E5 + 10;
int a[N], backup[N];
int n;
typedef long long ll;
void read(){
    cin >> n;
    for(int i = 0; i < n; i ++ )    scanf("%d", &a[i]);
}
ll merge_sort(int l, int r){
    if(l == r)  return 0;
    int mid = l + r >> 1;
    ll res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    int i, j, k;
    i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) backup[k ++ ] = a[i ++ ];
        else{
            res += mid - i + 1;
            backup[k ++ ] = a[j ++ ];   
        }
    }
    while(i <= mid) backup[k ++ ] = a[i ++ ];
    while(j <= r)   backup[k ++ ] =a[j ++ ];
    for(i = l, k = 0; i <= r; i ++ )    a[i] = backup[k ++ ];
    return res;
}
int main(){
    read();
    cout << merge_sort(0, n - 1) << endl;
    return 0;
}