求逆序对：归并排序 & 树状数组-JZTXT

前言：什么是逆序对？

在合并两个序列时，由于我们已经递归下去完成排序了，所以进行合并的是两个有序序列。双指针，一个下标从 l 指向 mid，一个从 mid + 1 指向 r。对于两个指针所指的，不断将更小的那一个放到用来转运的新序列 b 中。若相等，就将靠前里的元素先放到新序列中（思考一下，这样保证了稳定性）。然后把剩下的塞进去，最后把新序列里的东西倒腾回去。

这是一个归并排序的码：

void msort(int l, int r)
{
    if(l >= r) return;
    int mid = (l + r) >> 1;
    msort(l, mid);
    msort(mid + 1, r);//递归排序 
    int k = 0;
    int i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j]) b[++ k] = a[i ++];//稳定性
        else b[++ k] = a[j ++];
    }
    while(i <= mid) b[++ k] = a[i ++];//把剩余的部分加进去 
    while(j <= r) b[++ k] = a[j ++];
    for(int i = l; i <= r; i ++ ) a[i] = b[i - l + 1];//最后转移到原数组，完成合并
}

讲了这么多，逆序对到底怎么求？其实看一看归并中，这个合并的过程，我们就发现过程中就体现出了逆序对。

合并的是两段，a[i] 表示前半段，a[j] 表示后半段。合并过程中若 a[j] < a[i] 说明什么？说明这就是逆序对啊。由于这两段都有序了，所以从 a[i] ~ a[mid] 这一段的所有元素都对 a[j] 构成逆序对。这就出来了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n;
ll ans;
int a[N], b[N];
void msort(int l, int r)
{
    if(l >= r) return;
    int mid = (l + r) >> 1;
    msort(l, mid);
    msort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j]) b[++ k] = a[i ++];
        else
        {
            b[++ k] = a[j ++];
            ans += mid - i + 1;
        }
    }
    while(i <= mid) b[++ k] = a[i ++];
    while(j <= r) b[++ k] = a[j ++];
    for(int i = l; i <= r; i ++ ) a[i] = b[i - l + 1];
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    msort(1, n);
    printf("%lld", ans);
}

归并求逆序对

提供一个板子题：洛谷 P5149 会议座位

好久之前就加到题单里了，那时候正在学字典树。但由于忘了逆序对怎么求了（嘲讽一下）所以一直没写。今天一看发现是板子。

读完题你就发现这不就是求逆序对吗，只不过我们学的是数字，这里是字符串。

其实不用字典树，麻烦了。你只需要将每个字符串 map 一下就能转换成数字了。然后就是板子。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
ll ans;
int n;
int a2[N], b[N];
string s;
map<string, int> a1;
void msort(int l, int r)
{
    if(l >= r) return;
    int mid = (l + r) >> 1;
    msort(l, mid);
    msort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(a2[i] <= a2[j]) b[++ k] = a2[i ++];
        else
        {
            b[++ k] = a2[j ++];
            ans += mid - i + 1;
        }
    }
    while(i <= mid) b[++ k] = a2[i ++];
    while(j <= r) b[++ k] = a2[j ++];
    for(int i = l; i <= r; i ++ ) a2[i] = b[i - l + 1];
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ )
    {
        cin >> s;
        a1[s] = i;
    }
    for(int i = 1; i <= n; i ++ )
    {
        cin >> s;
        a2[i] = a1[s];
    }
    msort(1, n);
    printf("%lld", ans);
}

树状数组求逆序对。是树状数组主要的一大用途了。未完待续。

逆序数组promotion counting