题目

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

本文题目：逆序对的数量

代码

代码详解

#include<iostream>
using namespace std;
typedef long long LL ;  //定义long long 类型起个自定义名称！
const int N = 1e5 + 10;
int a[N],tmp[N];

LL merge_sort(int a[],int l,int r){
    if(l >= r) return 0;
    int mid = l + r >> 1 ;
    LL res = merge_sort(a, l, mid) + merge_sort(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{
            // cout<<"a[i]="<<a[i] << " " <<"a[j]="<<a[j] << " " <<"i = "<< i << " " << "mid = " << mid << endl;
            res += mid - i + 1;  //满足逆序对条件
            tmp[k++] = a[j++] ;
        } 
    }
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];

    for(int i = l , j =0; i <= r ; i++ , j++) a[i] = tmp[j];
    return res;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i ++) scanf("%d",&a[i]);
    cout << merge_sort(a,0,n-1) << endl ;
    return 0;
}

分析关键代码：

LL res = merge_sort(a, l, mid) + merge_sort(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{
            // cout<<"a[i]="<<a[i] << " " <<"a[j]="<<a[j] << " " <<"i = "<< i << " " << "mid = " << mid << endl;
            res += mid - i + 1;  //满足逆序对条件
            tmp[k++] = a[j++] ;
        } 
    }

LL res = merge_sort(a, l, mid) + merge_sort(a, mid + 1 , r);

之所以要将其相加，是因为我们分别递归处理左右两边，可能右边有逆序对，而左边也能构成逆序对，要把数量相加，下面用具体的例子演示

• input

2 3 4 5 6 1

• output

a[i]=5 a[j]=1 i = 3 mid = 4
a[i]=2 a[j]=1 i = 0 mid = 2

关键在于理解递归的流程，根据输出可以看到，当递归到右半部分时, 由于 5 > 1, 即代表 5,6 均 > 1， 则将 $res += mid - i + 1;$
将整段数据归并时，2 > 1, 即代表2,3,4 均 > 1, 则 $res += mid - i + 1;$

• 说明

这道题我一开始试图用两层$for$，后来发现复杂度太高，没法通过,用归并可降低复杂度。
注意本题数据的范围，逆序对数最大为：$\frac{n(n-1)}{2}$ > $INT\_MAX$,选用$long long$
归并代码的最后一句：$for$循环将整个范围复制回去，所以截止条件为：i <= r