D. Swap Dilemma 详细题解

题目重述

给定两个长度均为 $n$ 的数组 $a$ 和 $b$，元素均为互不相同的正整数。每次操作可以选择 $a$ 中的两个下标 $l \le r$，交换 $a_l$ 与 $a_r$；同时选择 $b$ 中的两个下标 $p \le q$，满足 $r-l = q-p$，交换 $b_p$ 与 $b_q$。问能否通过若干次（含零次）操作使 $a$ 与 $b$ 完全相同（即对应位置元素相等）。

核心观察

• 由于元素互异，将数组视为排列。若 $a$ 与 $b$ 的元素集合不同，则显然不可能变成相同，直接输出 NO。
• 当元素集合相同时，我们可以将元素离散化：将每个元素映射为它在排序后的秩（$1$ 到 $n$）。这样 $a$ 和 $b$ 转化为两个排列 $P$ 和 $Q$（长度为 $n$）。问题转化为：能否通过操作使 $P$ 变成 $Q$。

操作对排列奇偶性的影响

一个排列的逆序对数的奇偶性称为该排列的奇偶性（或符号）。交换排列中的两个不同元素（即执行一次对换）会改变逆序对数的奇偶性（奇变偶，偶变奇）。因此，任何一次交换都会翻转排列的奇偶性。

在题目的一次操作中：

• 我们在 $a$ 中交换两个元素（相当于对 $P$ 执行一次对换），
• 同时在 $b$ 中交换两个元素（相当于对 $Q$ 执行一次对换）。

因此，这次操作会同时翻转 $P$ 的奇偶性和 $Q$ 的奇偶性。于是，两个排列奇偶性的差值（相同则差为 $0$，不同则差为 $1$）在每次操作后保持不变。

初始时，若 $P$ 与 $Q$ 的奇偶性不同，则无论怎么操作，它们的奇偶性始终不同。而最终要求 $P = Q$，此时两者的奇偶性必然相同。因此，奇偶性不同是不可能的充要条件之一。

奇偶性相同是否充分？

答案是肯定的。可以证明：只要元素集合相同且 $P$ 与 $Q$ 的奇偶性相同，就能通过一系列合法操作将 $P$ 变为 $Q$。构造思路如下：

• 利用长度为 $1$ 的交换（即交换相邻元素）可以生成整个对称群（因为相邻对换生成所有置换）。但操作要求同时交换 $a$ 和 $b$ 中相同距离的两个位置。然而我们可以通过组合操作来模拟“单独在 $a$ 上执行一次相邻交换，而保持 $b$ 不变”的效果。例如，先在 $a$ 上交换相邻元素 $i$ 和 $i+1$，同时在 $b$ 上交换两个相邻元素 $j$ 和 $j+1$（距离也是 $1$）；然后再进行一次相反的操作（比如在 $b$ 上再换回来，同时 $a$ 上不执行交换）。但 $a$ 上不执行交换意味着我们要在 $a$ 上交换两个相同位置（$l=r$），这种退化交换虽然允许（$l=r$ 时 $r-l=0$，则 $b$ 中需选择 $p=q$，即无实际交换），但这不会改变 $a$。所以我们可以先在 $a$ 上做一次交换，同时在 $b$ 上做一次不影响结果的“空交换”（$p=q$），这样只改变了 $a$。随后再在 $b$ 上做一次交换，同时 $a$ 上做一次“空交换”，就只改变了 $b$。因此，通过组合，我们可以独立地 $a$ 或 $b$ 上执行任意交换（只要交换距离相同，但我们可以先用距离 $0$ 的交换来改变其中一个数组，再用距离 $1$ 的交换来改变另一个）。更严谨的证明是利用了：长度为 $0$ 的交换（即不交换）是允许的，因此我们可以先单独对 $a$ 做一系列相邻交换（每次用距离 $1$，同时 $b$ 上用距离 $1$ 但交换相同元素，即 $p=q$，相当于无变化），然后单独对 $b$ 做相邻交换。由于相邻交换足以生成所有排列，我们就能将 $a$ 变为任意我们想要的排列，同时将 $b$ 变为另一个排列。最后，由于初始 $P$ 和 $Q$ 奇偶性相同，我们可以通过一系列相邻交换将 $P$ 变成 $Q$，而在这个过程中，我们只需在 $a$ 上执行这些交换，同时在 $b$ 上执行相反的交换（即把 $b$ 中本应变化的部分抵消掉）。实际上，一个更简单的结论是：利用长度为 $1$ 的交换并允许在 $b$ 上同时做任意交换（包括空交换），我们可以实现在 $a$ 上的任意置换，同时保持 $b$ 不变；同理可实现 $b$ 上的任意置换。因此只要两个排列奇偶性相同，就能让它们变得相等。

因此，奇偶性相同是充分必要条件。

算法步骤

1. 对于每个测试用例：
   • 读入 $n$ 及数组 $a,b$。
   • 检查 $a$ 和 $b$ 的元素是否相同（排序后比较）。若不同，输出 "NO"，继续下一个测试用例。
2. 将 $a$ 和 $b$ 中的元素离散化：将元素值映射为 $1$ 到 $n$ 的序号（按升序）。得到排列 $P$ 和 $Q$。
3. 分别计算 $P$ 和 $Q$ 的逆序对数的奇偶性（即排列的符号）。可以使用树状数组（或归并排序）在 $O(n \log n)$ 时间内计算逆序对数，但只需奇偶性，可用异或优化。
4. 若 $P$ 和 $Q$ 的奇偶性相同，输出 "YES"，否则输出 "NO"。

复杂度分析

• 排序检查集合：$O(n \log n)$。
• 离散化映射：$O(n \log n)$。
• 计算逆序对奇偶性：$O(n \log n)$，可用树状数组或归并排序。
• 所有测试用例的 $n$ 总和 $\le 10^5$，总复杂度 $O(\sum n \log n)$，完全可行。

正确性总结

• 必要性：每次操作同时翻转两个排列的奇偶性，因此两者奇偶性差为不变量。最终相等时奇偶性相同，故初始必须相同。
• 充分性：当元素集合相同且奇偶性相同时，可以通过构造（利用长度为 $0$ 和长度为 $1$ 的交换）独立地在 $a$ 上执行任意交换，从而将 $a$ 逐步变成 $b$，同时保持 $b$ 不变（或同步调整），故一定可行。

因此，该解法正确且高效。