【每日算法】基础算法——归并排序[求逆序对的数量]（四）

题目内容

给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1≤n≤100000

输入样例

6
2 3 4 5 6 1

输出样例

题解

整个题根据归并排序算法+分治的思想来求解。

我们将整个序列均分成前后两个部分。将所有的逆序对分成以下三种情况，分别是：

逆序对中的两个数在前一个区间
逆序对中的两个数在后一个区间
逆序对中的两个数一个数在前一个区间，一个数在后一个区间。

当然，这里需要说明一个问题，那就是前两种情况其实在递归中转化为了第三种情况，比如有个逆序对在前一个区间里，当进行递归之后，这两个数字最终会被切割成两个区间的数字，变为第三种情况，基于此，题目的代码只需要编写对第三种的情况就可，这种结合很巧妙。同时，merge_sort函数的返回定义为逆序对的数量，因此，左右两边是个子问题，所以两个函数递归完就可以求出左右两个区间内部的逆序对数了。由于归并排序的过程中对序列进行了排序，因此前一个区间中的i代表的数若大于后一个区间j代表的数，那么此时针对j代表的数的逆序对的数量为mid-i+1。

需要注意的点

由于数据范围是10万，逆序对的数量最多为 10^5x(10^5 -1)/2，大概是 5x10^9 ，这个数值大于int的最大值，因此在代码层面，需要用long long类型来进行求解。

代码实现

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int q[N],tmp[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 k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k++] = q[i++]; // 当q[i]小于q[j]，则不作处理
        else{
            tmp[k++] = q[j++];
            res += mid-i+1; // 当q[i]大于q[j],则说明i后的全部数字大于q[j]，因此针对q[j]来说，逆序对数量为mid-i+1
        }
    //扫尾
    while(i<=mid) tmp[k++] = q[i++]; // 此时的情况说明上面的while是后面的区间遍历完成，前面的区间仍然没有遍历完，因此需要对前面的区间进行扫尾工作。
    while(j<=r) tmp[k++] = q[j++]; // 反之亦然
    
    for (int i=l, j=0; i<=r; i++,j++) q[i]=tmp[j]; // 将临时数组的排列后的有序数组存入q中，保证递归循环后的q的前后两个区间内部有序。
    
    return res;
}

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