自动搬运

查看原文

来自洛谷，原作者为

	songhongyi 懒

搬运于2025-08-24 22:59:45，当前版本为作者最后更新于2024-06-19 09:28:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part I： 注意到查询的过程，每轮操作会断掉一个环，因此返回的结果为 $n - c$，其中 $c$ 为置换环数。

Part II： 考虑对于每对在同一个置换环内的点，将其交换拆开，显然枚举所有对并且能操作就操作，会让置换环数变为 $n$。这样操作次数为 $\Theta(n^2)$，可以通过 Subtask 2。

Part III： 考虑二分。我们对每个 $i$ 二分出前面的第一个 $j$，满足 $i,j$ 在同一个置换环内即可。那么我们需要一次查询，查询在 $0,1,\cdots, j$ 中有没有和 $i$ 在同一个置换环内的点。考虑构造 $p_1,p_2,\cdots,p_{j}, p_i, p_{j+1},p_{j+2}\cdots p_{i-1},p_0,p_{i+1},p_{i+2},\cdots$ 即可。