# 交换之后的复原 — 题解

采用 Keeler 的双辅助构造；[Evans、Huang 与 Nguyen 的论文](https://arxiv.org/abs/1204.6086) 讨论了该方法及进一步改进。Codex（GPT-6）负责本题规格、构造的程序化、状态跟踪证明和独立检查器，不将这一已有方法署为原创。

## 将最终状态分成环

先模拟历史，令 $p[u]$ 表示身体 $u$ 当前的思想编号。它是一个排列。沿 $p$ 分解出长度至少为二的环，固定点无需处理。对一个环记为 $a_1,\ldots,a_t$ ，约定身体 $a_i$ 内是思想 $a_{i+1}$ ，最后身体内是思想 $a_1$ .设辅助身体为 $x=N+1,y=N+2$ .

对该环依次输出：

1. 交换 $(x,a_1)$ .
2. 交换 $(y,a_t)$ .
3. 对 $i=2,\ldots,t$ ，依次交换 $(x,a_i)$ .
4. 交换 $(y,a_1)$ .

共 $t+2$ 次。所有环处理完后，若非平凡环数为奇数，再交换 $(x,y)$ 一次。

## 跟踪每个思想

设处理本环前，两个辅助身体内的思想为 $X,Y$ ，它们可能已互换。第一步后，$x$ 得到 $a_2$ ，$a_1$ 暂存 $X$ .第二步后，$y$ 得到 $a_1$ ，$a_t$ 暂存 $Y$ .

第三步开始，$x$ 每次携带的恰好是下一个目标身体的正确思想；交换后该身体复原，$x$ 接手下一个思想。最后它把 $a_t$ 送回，并取走 $Y$ .第四步把 $a_1$ 送回，$y$ 取走 $X$ .因此本环全部复原，两位辅助者仅互换思想，其他身体未变。最后按奇偶性决定是否交换辅助者，就能全部复原。

## 合法性、次数与复杂度

每一新增交换都涉及辅助身体，所以不会重复历史中的身体对。一个环内的所有对互异；不同环使用不同普通身体；辅助者之间只可能最后交换一次。

设非平凡环数为 $c$ ，参与这些环的普通身体数为 $s$ .总次数是 $s+2c+(c\bmod2)$ .由于每环至少两个身体，$2c\le s\le N$ ，所以不超过 $2N+1$ .分解、构造及输出均为 $O(N+M)$ 时间，保存排列、访问状态和输出用 $O(N)$ 空间。

[std.cpp](std.cpp) 按环独立处理，证明与实现都较直接。[联合处理多个环](solution-alternative.zh.md) 可在 $c\ge3$ 时减少输出步数，两种方法均满足本题上限。

## 特殊评测

执行 `python checker.py input.in contestant.out` .检查器用集合记录历史与新增的无序身体对，逐步交换思想，最后检查包括辅助者在内全部复原。它还拒绝错误次数、越界编号、自交换、重复对、缺项和多余记号。返回码零表示接受，一表示拒绝。检查器额外存储全部历史对，因此自身空间是 $O(N+M)$ .

[题面](statement.zh.md) · [正式数据计划](tests/plan.json) · [生成器](tests/generate.py) · [测量记录](../../../docs/benchmark-R33.json)