B. 最小化逆序对 题解

题意回顾

我们有两个长度为 $n$ 的排列 $a$ 和 $b$。每次操作可以选择两个下标 $i$ 和 $j$，同时交换 $a_i$ 与 $a_j$ 以及 $b_i$ 与 $b_j$。目标是经过若干次操作后，使得两个排列中的逆序对总数尽可能小，并输出任意一个达到最小值的最终排列对。

核心观察

由于每次操作同时作用于两个排列的相同位置，因此无论进行多少次操作，每个下标上的数对 $(a_i, b_i)$ 始终作为一个整体一起移动。换言之，我们只能对这 $n$ 个数对进行任意重排，而不能改变每个数对内部的对应关系。

我们的目标是让 $a$ 和 $b$ 中的逆序对总数最小。考虑两个下标 $i$ 与 $j$（$i < j$）：

• 若 $a_i > a_j$ 且 $b_i > b_j$，则当前在 $a$ 和 $b$ 中各产生了一个逆序对（共 $2$ 个）。若交换这两个位置上的数对，则 $a$ 和 $b$ 中的这两个逆序对都会消失，逆序对总数减少 $2$。
• 若 $a_i > a_j$ 但 $b_i < b_j$，则交换会减少 $a$ 的逆序对、增加 $b$ 的逆序对，总数不变。
• 若 $a_i < a_j$ 且 $b_i > b_j$，交换同样使总数不变。
• 若 $a_i < a_j$ 且 $b_i < b_j$，交换会使总数增加 $2$。

因此，为了最小化总逆序对数，我们希望避免出现 $a_i$ 与 $a_j$ 的大小关系同 $b_i$ 与 $b_j$ 的大小关系 不一致 的情况。最理想的状态是：对于任意 $i < j$，都有 $(a_i - a_j)(b_i - b_j) \ge 0$，即两个序列的 相对顺序完全相同。此时两个序列同序，交叉抵消的逆序对不再存在，总逆序对数达到下界。

如何才能达到这种同序状态呢？一个简单的办法是将所有数对按 $a$ 的值从小到大排序。此时 $a$ 变成完全升序，逆序对数为 $0$；而 $b$ 则被动的跟着 $a$ 排序，其逆序对数由它自身的相对顺序决定，无法再减少（因为任何改变都会打破 $a$ 的有序性，从而引入 $a$ 的逆序对）。可以证明，这样得到的总逆序对数就是全局最小值。

结论：将 $(a_i, b_i)$ 看作一个整体，按 $a_i$ 升序排列，得到的 $a$ 和 $b$ 即为最优解之一。

算法步骤

1. 读入 $n$ 以及排列 $a$ 和 $b$。
2. 构造数对数组 pair<int,int> ab[n]，其中 ab[i] = {a[i], b[i]}。
3. 对 ab 数组按第一个元素（$a$ 的值）进行升序排序。
4. 输出排序后的第一个元素序列作为新的 $a'$，第二个元素序列作为新的 $b'$。

时间复杂度：单次测试用例 $O(n \log n)$，总复杂度 $O(\sum n \log n)$，在 $\sum n \le 2 \times 10^5$ 的限制下可以轻松通过。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        pair<int,int> ab[n];
        for(int i = 0; i < n; ++i)
        {
            cin >> ab[i].first;
        }
        for(int i = 0; i < n; ++i)
        {
            cin >> ab[i].second;
        }
        sort(ab, ab + n);
        for(int i = 0; i < n; ++i)
        {
            cout << ab[i].first << ' ';
        }
        cout << "\n";
        for(int i = 0; i < n; ++i)
        {
            cout << ab[i].second << ' ';
        }
        cout << "\n";
    }
    return 0;
}

正确性简要证明

设我们得到的新排列为 $a'$ 和 $b'$，其中 $a'$ 已经有序（$a'_1 \le a'_2 \le \dots \le a'_n$）。任取另一种可达的排列对 $a''$ 和 $b''$，其总逆序对数记为 $I(a'') + I(b'')$。由于 $a'$ 的逆序对数为 $0$，只需证明 $I(b') \le I(a'') + I(b'')$。通过逆序对的性质可以证明：将数对按 $a$ 排序后，任何与原排列不同的顺序都会在 $a$ 中引入新的逆序对，而减少的 $b$ 中的逆序对数量不可能超过引入的 $a$ 中的逆序对数量（详细证明可利用逆序对的对称性）。因此排序后的结果必为最优。