思路

我们首先把\(a,b\)输入进一个数据结构，并且对这两个序列以高度为关键字排序。我们先来写出一组样例排序后的样子（数组下标为原本的位置）：\[\{1_3,2_1,3_2,4_4\}\]与\[\{1_3,2_2,3_1,4_4\}\]我们观察发现，显然我们可以进行离散处理。所以令\(mapping[]\)为离散数组，在两组排序后进行\(mapping[a[i].index] = b[i].index\)，便可以完成离散化。问题便转换为b数组要完成多少次变换才能与a相同（因为我们已经进行了离散化处理，\(mapping[]\)便可以在\(n\)范围内）。我们可以想到使用计算逆序对个数来解决这个问题。问题迎刃而解。

代码

// P1966.cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000200;
const int mod = 99999997;
#define ll long long
struct element
{
    int val, idx;
    bool operator<(const element &ele) const
    {
        return val < ele.val;
    }
} a[maxn], b[maxn];
int mapping[maxn], tmp[maxn], n;
int ans = 0;

void merge(int l, int mid, int r)
{
    int sa = l;
    int p = mid + 1;
    int bias = l;
    while (sa <= mid && p <= r)
        if (mapping[sa] < mapping[p])
            tmp[bias++] = mapping[sa++];
        else
            tmp[bias++] = mapping[p++], ans += (mid - sa + 1), ans %= mod;
    while (sa <= mid)
        tmp[bias++] = mapping[sa++];
    while (p <= r)
        tmp[bias++] = mapping[p++];
    for (int i = l; i <= r; i++)
        mapping[i] = tmp[i];
}

void mergeSort(int l, int r)
{
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    merge(l, mid, r);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i].val), a[i].idx = i;
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i].val), b[i].idx = i;
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++)
        mapping[a[i].idx] = b[i].idx;
    mergeSort(1, n);
    cout << ans;
    return 0;
}