题解：P10628 [JOI Open 2024] 图书馆 3

songhongyi · 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 即可。