hiho 學習日記：hiho一下 第三十九周 二分·歸并排序之逆序對

http://hihocoder.com/contest/hiho39/problem/1

分治法求逆序數

套用歸并排序并且記個數即可

AC代碼：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define LL long long

LL a[maxn];
LL ans = 0;
void Merge(int l, int mid, int r) {
    int b[maxn];
    int li = l, lj = mid + 1, len = 0;
    int cntb = 0;
    while(li <= mid && lj <= r) {
        if(a[li] <= a[lj]) {
            ans += cntb;
            b[len ++] = a[li ++];
        }else {
            cntb ++;
            b[len ++] = a[lj ++];
        }
    }
    while(li <= mid) {
        b[len ++] = a[li ++];
        ans += cntb;
    }
    while(lj <= r) {
        b[len ++] = a[lj ++];
    }
    for (int i = l; i <= r; i ++) {
        a[i] = b[i - l];
    }
}

void MergeSort(int l, int r){
    if(l < r) {
        int mid = (l + r) >> 1;
        MergeSort(l, mid);
        MergeSort(mid + 1, r);
        Merge(l, mid, r);
    }
}

int main()
{

    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++)
        scanf("%lld", &a[i]);
    MergeSort(1, n);
    printf("%lld\n", ans);
    return 0;
}