归并排序求逆序对个数 $O(nlog(n))$

1. 贪心：首先我们可以不加证明的发现， a, b两个对应的第 i 小的元素排列在一起则可以满足结果
2. 对应的元素排列好以后，使用“绑定”的思想，然后归并排序的计算逆序对个数。

时间复杂度

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N=100010, mod=99999997;

PII a[N], b[N];
int n, c[N], ans;

void mergeSort(int l, int r){
    if(l>=r) return;
    int mid = l+r>>1;
    mergeSort(l, mid);
    mergeSort(mid+1, r);
    int i=l, j=mid+1, tmp[n+1], k=0;
    while(i<=mid && j<=r){
        if(c[i]<=c[j]){
            tmp[k++] = c[i++];
        }else{
            ans += mid-i+1;
            ans %= mod;
            tmp[k++] = c[j++];
        }
    }
    while(i<=mid) tmp[k++] = c[i++];
    while(j<=r) tmp[k++] = c[j++];
    for(int w=0; w<k; w++){
        c[l+w] = tmp[w];
    }
}
int main(){
    cin>>n;
    for(int i=1, tmp; i<=n; i++){
        cin>>tmp;
        a[i].first = tmp;
        a[i].second = i;
    }
    for(int i=1, tmp; i<=n; i++){
        cin>>tmp;
        b[i].first = tmp;
        b[i].second = i;
    }
    sort(a+1, a+n+1);
    sort(b+1, b+n+1);
    //现在我们只需要求 c[i]中逆序对的个数就是问题的解
    /*
    这个地方需要自己去举例子看
    c数组的作用是去绑定 b[i] 与 a[i] 中的元素
    比如现在假设 ：  
    a:   4 3 2 1
    b:   4 1 3 2

    那么 c 中对应好为：   idx:  1 2 3 4
                    c   value:  2 3 1 4  则a元素已经排列好，  对应的去算 c 中的逆序对个数
    */
    for(int i=1; i<=n; i++){
        c[b[i].second] = a[i].second; 
    }
    mergeSort(1, n);
    cout<<ans;
    return 0;
}