P15576 [USACO26FEB] Good Cyclic Shifts G

对于一个 $1\dots N$ 的排列 $p_1,p_2,\dots,p_N$（$1\le N\le 2\cdot 10^5$），定义 $f(p)=\sum_{i=1}^N \frac{|p_i-i|}{2}$。如果一个排列能够通过至多 $f(p)$ 次相邻元素交换变为 $p_i=i$（恒等排列，identity permutation）的排列，则称该排列是 **好的**。 给定一个排列，找出它的哪些循环移位是好的。

输入包含 $T$（$1\le T\le 10^5$）个独立的测试用例。每个测试用例的格式如下： 第一行包含 $N$。 第二行包含 $p_1,p_2,\dots,p_N$（$1\le p_i\le N$），保证是 $1\dots N$ 的一个排列。 保证所有测试用例的 $N$ 之和不超过 $10^6$。

对于每个测试用例，输出两行： 第一行输出好的循环移位的数量 $k$。 然后输出一行，包含 $k$ 个按升序排列的整数 $s$（$0\le s

考虑第二个测试用例，其中 $p = [1, 2, 4, 3]$。 - $f(p) = (|1 - 1| + |2 - 2| + |4 - 3| + |3 - 4|) / 2 = 1$。因为 $p$ 可以通过交换 $p_3$ 和 $p_4$ 一次操作变为恒等排列，所以 $p$ 是好的。 - 将 $p$ 向右循环移位 $1$ 次，得到 $q = [3, 1, 2, 4]$。$f(q) = (|3 - 1| + |1 - 2| + |2 - 3| + |4 - 4|) / 2 = 2$。因为 $q$ 可以通过将 $q_1$ 向前交换两步变为恒等排列，所以 $q$ 是好的。 可以看出另外两个循环移位不是好的。 ### 评分标准 - 输入 2：$N\le 10$ - 输入 3-5：$T\le 10, N\le 2000$ - 输入 6-11：无额外限制。 题目来源：Akshaj Arora 翻译由 DeepSeek 完成