归并排序与逆序对

· · 算法·理论

归并排序

大概思路就是二分先去划分，然后每一层都保证左边和右边是严格排序的再合并，利用递归

模板：

void mergeSort(int l, int r)
{
    if(l == r) return;
    int mid = (l+r)/2, i = l, j = mid+1, k = l;
    mergeSort(l, mid);
    mergeSort(mid+1, r);
    while(i <= mid && j <= r)
        if(s[i] <= s[j]) tmp[k++] = s[i++];
        else tmp[k++] = s[j++];
    while(i <= mid) tmp[k++] = s[i++];
    while(j <= r) tmp[k++] = s[j++];
    for(int x = l; x <= r; x++) s[x] = tmp[x];
}

应用场景一 求逆序对

P1908 逆序对

利用归并排序的特性，每次归并LR操作时两块都是严格递增的，只要发现L部分的L_i>R_j，那么L_{i+1}一直到L_{mid}应该都是大于R_j的，在此时统计逆序对即可

AC代码（参考题解）

#include <iostream>
#include <algorithm>
#define MAXN 500001
using namespace std;

int s[MAXN], tmp[MAXN];
long long ans;

void mergeSort(int l, int r)
{
    if(l == r) return;
    int mid = (l+r)/2, i = l, j = mid+1, k = l;
    mergeSort(l, mid);
    mergeSort(mid+1, r);
    while(i <= mid && j <= r)
        if(s[i] <= s[j]) tmp[k++] = s[i++];
        else tmp[k++] = s[j++], ans += mid - i + 1;
    while(i <= mid) tmp[k++] = s[i++];
    while(j <= r) tmp[k++] = s[j++];
    for(int x = l; x <= r; x++) s[x] = tmp[x];
}

int main()
{
    int n;
    cin >> n;
    for(int x = 1; x <= n; x++) scanf("%d", &s[x]);
    mergeSort(1, n);
    printf("%lld\n", ans);
    return 0;
}

参考资料：

动图讲解

P1908题解