归并排序求逆序数

逆序数：

例如：2 3 4 5 6 1

可以发现2和1, 3和1, 4和1, 5和1, 6和1都是逆序所以逆序对数量为5

不难发现逆序对数量即为一串乱序的数变为有序，所要经过两两交换的次数，即乱序的数到它有序时的位置的距离

求两两交换的次数，可以想到用冒泡排序去求，但是冒泡排序复杂度为n^2，数据量大时就不能用。例如数据量为1e6时，就不行了，所以可以用归并排序，在分治归并的过程中求出交换的次数（距离），时间复杂度为nlogn

思路：

归并排序求逆序数，我们发现只需在归并时进行一下判断即可。

归并时有两种情况，①a[i] <= a[j] 和 ②a[i] > a[j] ,第一种情况即左区间的数小于右区间的数，则没有逆序，第二种情况是出现了逆序，不难发现，应交换的次数（距离）为第一个区间还剩的数的数量，即mid - i + 1, 则通过归并之后，我们可以得到逆序对数量

代码：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

typedef long long ll;
int n;
ll res;
const int N = 1e6 + 10;
vector<int> a(N);
vector<int> tmp(N);

void solve(vector<int> &a, int l, int r) {
    if(l >= r) return;

    int mid = (l + r) >> 1;
    solve(a, l, mid);
    solve(a, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r) {
        if(a[i] <= a[j]) tmp[k ++] = a[i ++];
        else {
            tmp[k ++] = a[j ++];
            res += (mid - i + 1); // 求交换距离
        } 
    }
    while(i <= mid) tmp[k ++] = a[i ++];
    while(j <= r) tmp[k ++] = a[j ++];

    for(i = l, j = 0; i <= r; i ++, j ++) a[i] = tmp[j];
}

int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr);

    cin >> n;

    for(int i = 0; i < n; i ++) cin >> a[i];

    solve(a, 0, n - 1);

    cout << res;

    return 0;
}