一半重排

记错位位置的集合为 $M=\{i\mid P_i\ne i\}$，并令 $m=|M|$。

若 $m=0$，答案为 $0$。

若 $1\le m\le N$，答案为 $1$。选择所有错位位置，再任意补充固定点直到恰好选择 $N$ 个位置，一次重排即可全部排好。

下面设 $m>N$。设两次重排选择的位置集合分别为 $A,B$。由于 $|A|=|B|=N$，有

$$|A\cap B|=|\{1,\cdots,2N\}\setminus(A\cup B)|.$$

位于 $A\cup B$ 之外的位置从未被操作，因此它们一开始就必须是固定点。

若至少存在一个固定点，则答案为 $2$。因为 $m>N$，一次重排不可能完成；另一方面，可以让一个固定点同时位于两次选择集合之外，从而总能在两次重排内完成排序。

接下来考虑不存在固定点的情况。此时 $A\cup B$ 外不能有任何位置，因此上式迫使 $A\cap B=\varnothing$，即 $A,B$ 恰好把全部位置分成两部分。$A$ 中的位置只会在第一次重排中被操作，所以第一次重排结束后它们必须已经全部正确。

将排列分解成若干个环。如果 $A$ 只包含某个环的一部分，那么其中至少有一个位置所需要的值仍位于 $B$ 中。因此 $A$ 必须是若干完整环的并。反过来，如果存在若干环的长度之和恰好为 $N$，第一次重排排好这些环，第二次重排排好其余环即可。

所以在不存在固定点时，两次重排可行当且仅当某些环长之和恰好为 $N$。这可以用子集和 DP 在 $O(N^2)$ 时间内判断。

若存在这样的子集，答案为 $2$；否则答案为 $3$。后一种情况下，两次重排由上述必要条件可知不可能；另一方面，可以先用一次重排制造一个固定点，再利用存在固定点的情况，最多再用两次即可完成。

因此答案始终属于 $0,1,2,3$。每个测试用例的时间复杂度为 $O(N^2)$，空间复杂度为 $O(N)$。

Solution written by GPT5.6