归并排序求逆序对

解题思路:

首先我们给出逆序对的定义：

对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对。

重要的地方在于，一个元素可以不只是在一个逆序对中存在。如果 k > j > i 且 a[i] > a[j] > a[k]，那么这里

有两个含 a[i] 的逆序对，分别是 (a[i], a[j]) 和 (a[i], a[k]), a[i]是可以使用多次的。

那么第二步是分析问题，求逆序对的过程是两个数的比较，我们的归并排序算法是把原数组划分成两个子数组的过程，并将两个有序数组合并成一个更大的有序数组，我们可以在排序的过程求逆序对的数量。

我们将序列从中间分开，将逆序对分成三类：

1.逆序对的两个元素都在左边；

2.逆序对的两个元素都在右边；

3.逆序对的两个元素一个在左一个在右；

因此这就是我们算法的大致框架：

计算逆序对的数量（序列）：

1. 递归算左边的；

2. 递归算右边的；

3. 算一个左一个右的；

4. 把他们加到到一起。

这个时候我们注意到一个很重要的性质，左半边和右半边排序次数相加也就是我们逆序对的一部分，另一部分逆序对元素一左一右的数量，左右半边的元素在各自任意调换顺序，是不影响第三步计数的，因此我们可以数完就给它排序。这么做的好处在于，如果序列是有序的，会让第三步计数很容易。

比如序列是这样的

4 5 6 | 1 2 3

左半边和右半边都排好序了，当你发现4比1还大时，也就说明4之后的数5，6也比1大，也构成逆序对，这也是mid - i +1的由来，把已经求好的那部分再相加起来就是结果了。

注意事项:用cin>>可能会超时

参考代码:

#include<iostream>

using namespace std;

typedef long long LL;

const int N = 500010;

int q[N],tmp[N];

int n;

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 = l, j = mid + 1, k = 0;

    while(i <= mid && j <= r)  //其余部分的逆序对数

    {

        if(q[i] <= q[j]) tmp[k++] = q[i++];

        else

        {

            tmp[k++] = q[j++];

            res += mid - i + 1;

        }

    }

    while(i <= mid) tmp[k++] = q[i++]; //归并排序收尾

    while(j <= r) tmp[k++] = q[j++];

    for(int i = l, j = 0; i <= r; i++, j++)

        q[i] = tmp[j];

    return res;

}

int main()

{

    scanf("%d",&n);

    for(int i = 0; i < n; i++)

        scanf("%d",&q[i]);

    printf("%lld\n",merge_sort(0, n - 1));

}