2023/1/27 逆序对的数量

逆序对定义

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

分析
若将序列从中间划分，可以分为3类：

1. 某逆序对的两个元素都在左边
2. 某逆序对的两个元素都在右边
3. 某逆序对的两个元素一个在左，一个在右
   算法框架
4. 递归计算左边逆序对数量merge_sort(q, l, mid)
5. 递归计算右边逆序对数量merge_sort(q, mid + 1, r)
6. 计算第三种情况的逆序对数量
7. 把他们加到一起
   结合归并思想
   如果左右两边的序列各自有序，第 3 中情况就容易计算的多
   比如序列是这样的

4 5 6 | 1 2 3
当你发现 4 比 3 大的时候，也就是说右边最大的元素都小于左边最小的元素，那么左边剩下的5和6都必然比右边的所有元素大，因此就可以不用数5和6的情形了，直接分别加上右半边的元素个数就可以了，这一步就降低到了
O(n), 我们知道递归式 T(n) = O(logn)*O(n) = O(nlogn)的，所以排序的成本是可以接受的，并且这一问题下，
可以很自然地使用归并排序。
代码

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int q[N], n;
LL merge_sort(int q[],int l,int r){
    if(l >= r) return 0;
    
    int mid = l + r >> 1;
    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    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(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
    return res;
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> q[i];
    cout << merge_sort(q, 0, n-1);
    return 0;
}