ABC 436e 题解

· · 题解

首先 AC 代码：https://atcoder.jp/contests/abc436/submissions/71721931

时间看上去比较劣，大概是 IO 使用 read 太慢的缘故。

这篇题解就是为了这些私货而生的。

这个东西赛前恰好做过原题：CF1768D。套路非常类似。

具体而言考虑把排列视作一个置换：i \to p_i，分解为若干不同轨道。由于集合是有限的，所以每个轨道都是一个轮换。

根据函数图的经典结论，我们知道交换一个环上的两个点可以将环分裂，交换不同环的点会将两个环合并到一起。

我们的目标是将原始图变成一堆自环（消除掉所有尺寸大于 1 的环），这样我们发现，肯定在所有操作都是“有用的”的时候总操作次数最少。

也就是说，如果每次操作都将一个环分裂，这样操作次数最少。

那么我们的第一次操作可能是哪些呢？事实上你随便挑一个能够将环分裂的操作都行。

那么答案就随便求了：\sum_{\text{for all cycles}} c(c-1)/2，其中 c 是轮换的大小。

然后回到那个结论。我们需要证明：交换同一个环上的两个不同点，环被分裂成两个。而交换不同环上的两个点，两个环合并。

考虑 i, j 是同一个环上的两个点。设前驱分别为 v_i, v_j。交换 i 和 j 本质上相当于让 v_i 指向 j 而 v_j 指向 i。

那么，就变成了 v_i \to j \to p_j \to \dots，注意到原本这也是一个环，也就是说那串省略号最后会绕回 v_i，这就成了一个环。而另一边同理，并且你会发现两个环没有交集。

对于 i 与 j 不在同一个环上的情形，那串省略号不再通向 v_i，而是通向 v_j，又从 v_j 绕到 i，所以两个环就并成了一个。