1.787. 归并排序 - AcWing题库

① 确定分界点 mid = l + r >> 1

② 递归排序 左边右边

③ 合并有序数组

模板：

void merge_sort(int q[], int l, int r){
    if(l >= r)    return 0;
    
    int mid = l + r >> 1;
    
    merge_sort(q, l ,mid), merge_sort(q, mid+1, r);
    
    int i = l, j = mid+1, k =0;
    // 归并
    while(i <= mid && j <= r)
        if(q[i] < q[j])     tmp[k++] = q[i++];
        else     tmp[k++] = q[j++];
    
    // 扫尾
    while(i <= mid)    tmp[k++] = q[i++];
    while(j <= r)    tmp[k++] = q[j++];
    
    // 物归原主
    for(int i = l, j = 0; j < k; i++, j++)    q[i] = tmp[j];
}
 
int main(){
    merge_sort(q, 0, n-1);
}

tmp数组用来存放有序的部分

2.788. 逆序对的数量 - AcWing题库

首先看题目，知道什么是逆序数对。

可以一边归并排序一边计算有序数对

当i > j 并且 q[i] < q[j]的时候，因为这两部分都是有序数组。那么对于q[j]这个点，q[i]以后所有的数都可以跟q[j]构成逆序数对，所以针对q[j]这个数字可以构成的逆序数对有 res = mid - i  + 1 个，让然后左右两边都这么递归计算就好。

注意题目的范围是100000，当最差的情况是这个数组是逆序的，等差数列求和算一下逆序对数量会超过INT_MAX

#include<iostream>
using namespace std;

const int N = 1e5+10;

typedef long long ll;
ll q[N], tmp[N];

ll merge_sort(ll l, ll r){
    if(l >= r) return 0;
    
    ll mid = l + r >> 1;
    ll res = merge_sort(l, mid) + merge_sort(mid+1, r);
    
    ll i = l, j = mid+1, k = 0;
    
    
    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(int i = l, j = 0; j < k; i++,j++) q[i] = tmp[j];
    
    return res;
}

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