分治算法——逆序对

逆序对

在一个有n个元素的一维数组中，若其中第i个数前面有m个数比i大，即对于第i个数有m个逆序对。以此类推，将整个数组中的所有逆序对个数统计出来

对于该题，暴力算法显然不是一个好方案。但我们可以简化问题。对于一个数组，求其逆序对可以分别求其每个分数组的逆序对数，再进行合并（实际就是归并排序）

例如：
数组长度： 6
左侧：5，8，9 （下标为 i）
右侧：1，4，7 （下标为 j）
两侧均为有序的，则只要找出右侧有多少逆序对即可
对于5，有5>1, 5>4, 有逆序对产生，而左侧5最小，故有mid-i+1(此处i为5的位置1）对逆序对。
而对于5<7,则没有逆序对产生，右侧下标 j++。
当5被遍历完，再左侧下标 i++。

大体思路如上，再加上归并排序的思想，直接上代码：

#include <iostream>

using namespace std;

typedef long long ll;

int a[500010], b[500010];
int num;

void merge_sort(int left, int right)
{
    if (left == right)
        return;
    int mid = (left + right) / 2;
    int i = left, j = mid+1, k = left;
    merge_sort(i, mid);
    merge_sort(j, right);
    while (i <= mid && j <= right)
    {
        if (a[i] <= a[j])
            b[k++] = a[i++]; 
        else
        {
            b[k++] = a[j++];
            int m = mid - i;
            m += 1;
            num += m;
        }
    }
    while (i <= mid) b[k++] = a[i++];
    while (j <= right)b[k++] = a[j++];

    for (int l = left; l <= right; l++)
        a[l] = b[l];

}



int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    merge_sort(1, n);
    cout << num << endl;
    return 0;
}

运行结果如下

如果不太了解什么是归并排序，可以看看鄙人的CSDN（可能写的也不清楚。。。反正我是懂了?）：https://blog.csdn.net/KrMzyc/article/details/113090643