本题第一篇题解存在问题

link

存在问题的原因：

题解没有最小化操作数，针对做法构造数据可以将操作数卡到 $5 \times 10^5$ 以上。

题解的原理是按照顺序把从 $1$ 到 $n$ 的数换回自己的位置，在精心构造的数据下，可以让他的交换次数被卡到很大。

构造的方式是：先把 $1 \sim \dfrac{n}{2}$ 的数按照顺序放在最后面。然后将 $\dfrac{n}{2} + 1$ 到 $\dfrac{3n}{4}$ 的数按照顺序放在刚才放的位置前面，然后把 $\dfrac{3n}{4} + 1$ 到 $\dfrac{7n}{8}$ 的数按顺序放在刚才放的数前面，以此类推。这样的操作能最大化交换次数，轻松卡到 $5 \times 10^5$ 以上。

对此我想到的一个解决方案是：不能按顺序从 $1$ 到 $n$ 把所有数换回自己的位置，可以自己 random 一下决定换的顺序，这样就无法强行构造数据卡掉该做法了。

hack 数据比较长，放在二楼：