P1908 逆序对（归并排序）

https://www.luogu.com.cn/problem/P1908

归并排序是用来求逆序对的

归并排序的思想就是分治

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 10;
int n,a[maxn],c[maxn];
int ans;
void msort(int l,int r){
    if(l == r)
        return ;
    int i = l,mid = (l + r) / 2,j = mid + 1;
    msort(l,mid);msort(mid + 1,r);
    int k = l;
    while(i <= mid && j <= r){
        if(a[i] <= a[j])
            c[k++] = a[i++];
        else{
            c[k++] = a[j++];
            ans += mid - i + 1;
        }
    }
    while(i <= mid)
        c[k++] = a[i++];
    while(j <= r)
        c[k++] = a[j++];
    for(int z = l; z <= r;z++)
        a[z] = c[z];

}
signed main(){
    //freopen("in","r",stdin);
    ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    msort(1,n);
    cout << ans;
    return 0;
}