形式化题目

给定两个长度为 $n$ 的序列 $a_1,\dots,a_n$ 与 $b_1,\dots,b_n$，各自内部元素互不相同（两列的取值集合可以不同，样例 2 的 $b$ 里就有 $a$ 中没有的高度 $7$）。当前配对下的距离定义为

每次操作可以交换同一列内相邻两根火柴的位置，两列各自独立地操作任意多次。求让 $D$ 达到最小值所需的最少总交换次数；答案可能很大，输出它对 $99\,999\,997$ 取模的结果。

样例 1：$a=(2,3,1,4)$，$b=(3,2,1,4)$，最小距离 $0$，输出 $1$。 样例 2：$a=(1,3,4,2)$，$b=(1,7,2,4)$，升序配对得到 $(1,1),(2,2),(3,4),(4,7)$，最小距离 $0+0+1+9=10$，输出 $2$。

正解

思路

朴素想法。 按题意直接贪心——每次挑一对“顺序不对”的相邻火柴交换——无法证明总次数最少、也不知道何时停止；能保证正确的朴素版本是：先定出目标配对，再用双重循环枚举 $i<j$ 数错位排列的逆序对，耗时 $O(n^2)$。下面先把“目标该长什么样、最少次数怎么刻画”讲清楚（第一、二步），再把数逆序对的瓶颈消掉（第四步）。

第一步：最小距离由什么决定。 交换不改变任一列的元素集合，所以 $\sum a_i^2$ 与 $\sum b_i^2$ 都是常数：

要 $D$ 最小就要 $\sum a_i b_{\pi(i)}$ 最大。由排序不等式，两序列同序配对时这个和最大，即第 $r$ 小的 $a$ 与第 $r$ 小的 $b$ 站在一起。把每列替换成自己的排名序列——第 $i$ 位记它在本列中是第几小（$1$ 基）——记作 $c$ 和 $d$。于是 $D$ 最小当且仅当两列同位同排名（$c$ 与 $d$ 逐位相等，目标形态可以是任意共同排列），因为距离只取决于谁和谁配对，与这对火柴站在哪个位置无关。

第二步：把交换次数变成逆序对。 一次相邻交换恰好交换排名序列的相邻两项。要把排列 $c$ 变成排列 $d$：$c$ 第 $i$ 位的元素在 $d$ 中的目标位置 $m_i$ 唯一确定，凡 $i<j$ 而 $m_i>m_j$ 的元素对都必须交换相对次序，而每次相邻交换恰好改变一对元素的相对次序；反向地，把错位排列 $m$ 冒泡成升序恰需 $\mathrm{inv}(m)$ 次相邻交换。所以最少次数就是错位排列的逆序对数——这是"相邻交换次数 = 排列逆序对数"的经典结论。

于是问题变成：选一个目标排列 $T$，最小化 $\mathrm{dist}(c,T)+\mathrm{dist}(d,T)$，其中 $\mathrm{dist}$ 是 Kendall 距离（把一个排列变成另一个所需的最少相邻交换次数）。它满足三角不等式 $\mathrm{dist}(c,d)\leqslant\mathrm{dist}(c,T)+\mathrm{dist}(d,T)$，取 $T=c$（第 1 列一动不动）时右端恰好等于 $\mathrm{dist}(c,d)$、取到下界。所以只重排一列就够了，答案就是 $\mathrm{dist}(c,d)$。

第三步：把 $\mathrm{dist}(c,d)$ 写成能算的逆序对。 展开来看：第 2 列第 $i$ 位的排名是 $d_i$，它要与第 1 列中排名 $d_i$ 的那根同位，记 $p_i$ 为那根火柴在第 1 列中的位置，即 $p=c^{-1}\circ d$；它与错位排列 $m=d^{-1}\circ c$ 互为逆排列，而一个排列与其逆的逆序数相同，所以答案就是 $p$ 的逆序对数。以样例 1 为例（位置 $1$ 基）：

$p=(2,1,3,4)$ 只有一对逆序 $(2,1)$，所以输出 $1$：不动第 2 列，只把第 1 列前两根交换一次即可。样例 2 同样验证：

$p=(1,3,4,2)$ 的逆序对是 $(3,2),(4,2)$，输出 $2$，与题面一致。

第四步：$O(n\log n)$ 数逆序对。 朴素双重循环在题面 $n\leqslant100\,000$ 时约 $5\times10^9$ 次比较，跑不完；高度可达 $2\times10^9$、两列取值集合又不同，也不能按键值开桶——排名只依赖比较，正好绕开这两个问题。计数用树状数组从左到右扫描 $p$：对 $p_i$ 查前缀和得到"已插入中 $\leqslant p_i$ 的个数"，"已插入总数 $-$ 该值"就是与 $p_i$ 构成的逆序对增量，然后把 $p_i$ 单点插入。每个位置两次 $O(\log n)$ 操作，先查后插的顺序保证统计的恰好是严格在它左边的元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=99999997;
void add(vector<int>&tr,int x){int n=tr.size()-1; while(x<=n){tr[x]++; x+=x&-x;}}
int sumq(vector<int>&tr,int x){int s=0; while(x){s+=tr[x]; x-=x&-x;} return s;}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int n; if(!(cin>>n)) return 0; vector<ll>a(n),b(n),sa,sb; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; sa=a; sb=b; sort(sa.begin(),sa.end()); sort(sb.begin(),sb.end()); map<ll,int> ra,rb; for(int i=0;i<n;i++){ra[sa[i]]=i+1; rb[sb[i]]=i+1;} vector<int> pos(n+1); for(int i=0;i<n;i++) pos[ra[a[i]]]=i; vector<int> tr(n+1); ll inv=0; for(int i=0;i<n;i++){int v=pos[rb[b[i]]]+1; int le=sumq(tr,v); inv += i - le; add(tr,v);} cout << inv%MOD << '\n'; return 0;}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 10:29
# update_at: 2026-10-02 10:29

import sys

MOD = 99_999_997  # 题面取模数：99,999,997


def rank_of(values: list[int]) -> dict[int, int]:
    """把一列高度映射成排名：最小的为 1（同列高度互不相同，无并列）。"""
    return {value: rank for rank, value in enumerate(sorted(values), 1)}


def count_inversions(order: list[int]) -> int:
    """树状数组统计逆序对数：依次插入各值，用"已插入个数 - 前缀和"得到比它大的个数。

    逆序对数 = 把 order 变为升序所需的最少相邻交换次数。
    """
    size = len(order)
    tree = [0] * (size + 1)
    inversions = 0

    for seen, value in enumerate(order, 1):
        le = 0  # 已插入中小于等于 value 的个数
        j = value
        while j:
            le += tree[j]
            j -= j & -j
        inversions += seen - 1 - le  # 已插入的比 value 大的个数

        j = value
        while j <= size:
            tree[j] += 1
            j += j & -j

    return inversions


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [next(data) for _ in range(n)]
    b = [next(data) for _ in range(n)]

    # 最小距离 ⇔ 两列按排名同位配对（排序不等式）；距离只取决于配对关系，
    # 所以把第 1 列原样当作目标排列，只重排第 2 列，总次数即两排列的 Kendall 距离。
    rank_of_a = rank_of(a)
    rank_of_b = rank_of(b)

    # 第 2 列第 i 根要与第 1 列同排名的那根同位，记下它在第 1 列中的位置
    pos_of_rank: dict[int, int] = {}
    for pos, value in enumerate(a):
        pos_of_rank[rank_of_a[value]] = pos
    order = [pos_of_rank[rank_of_b[value]] for value in b]

    # 下标从 0 起，平移成 1 起以适配树状数组
    print(count_inversions([pos + 1 for pos in order]) % MOD)


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O(n\log n)$——两列排序离散化 $O(n\log n)$，生成映射序列 $O(n)$，树状数组统计逆序对 $O(n\log n)$。
• 空间复杂度：$O(n)$，排名字典、映射序列与树状数组各占 $O(n)$。
• 答案上界 $\dfrac{n(n-1)}{2}\approx5\times10^9$，超过模数 $99\,999\,997$；Python 整数任意精度，计数过程中不必取模，输出前统一取模。

总结

• 最小距离 ⇔ 两列同位同排名：平方和展开后用排序不等式，且最小值只由配对关系决定，与目标排列的具体形态无关。
• 最少交换次数是排列之间的度量问题：三角不等式说明只重排一列即最优，答案 = 两列排名序列的 Kendall 距离。
• 把 Kendall 距离展开成"第 1 列中同排名伙伴的位置"这一排列，用树状数组 $O(n\log n)$ 数逆序对，最后对 $99\,999\,997$ 取模。