【归并排序】AcWing. 505 / NOIP2013提高组《火柴排队》（c++）

【题目描述】

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。

现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：

其中 ai  表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。 

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。

请问得到这个最小的距离，最少需要交换多少次？

如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

【输入格式】

共三行，第一行包含一个整数 n，表示每盒中火柴的数目。 

第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

【输出格式】

输出共一行，包含一个整数，表示最少交换次数对 99,999,997 取模的结果。

【数据范围】

1≤n≤10的5次方,
0≤火柴高度≤2的31次方−1。

【输入样例】

【输出样例】

对归并排序不熟悉的可以参考快速排序模板&归并排序模板及对应例题（C++）

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, MOD = 99999997;

int n;
int a[N], b[N], c[N], p[N];

void work(int a[])
{
    for (int i = 0; i < n; i ++ ) p[i] = i;
    sort(p, p + n, [&](int x, int y) {
        return a[x] < a[y];
    });
    for (int i = 0; i < n; i ++ ) a[p[i]] = i;
}

int merge_sort(int l, int r)
{
    if (l >= r) return 0;
    int mid = l + r >> 1;
    int res = (merge_sort(l, mid) + merge_sort(mid + 1, r)) % MOD;
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (b[i] <= b[j]) p[k ++ ] = b[i ++ ];
        else p[k ++ ] = b[j ++ ], res = (res + mid - i + 1) % MOD;
    while (i <= mid) p[k ++ ] = b[i ++ ];
    while (j <= r) p[k ++ ] = b[j ++ ];
    for (i = l, j = 0; i <= r; i ++, j ++ ) b[i] = p[j];
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < n; i ++ ) scanf("%d", &b[i]);

    work(a), work(b);
    for (int i = 0; i < n; i ++ ) c[a[i]] = i;
    for (int i = 0; i < n; i ++ ) b[i] = c[b[i]];

    printf("%d\n", merge_sort(0, n - 1));
    return 0;
}