A6910. 排列轮转排序
编程题
提高+/省选-
知识点
题目描述
给定一个长度为 $n$ 的排列 $a$。我们称下标 $i$ 是“好”的，如果满足 $a_i=i$。
每经过 $1$ 秒钟，我们将所有不是“好”的下标对应的元素**整体向右轮转一位**。具体来说：
- 设 $s_1,s_2,\dots,s_k$ 是所有不是“好”的下标，按从小到大排列；
- 对于每个 $i$ 从 $1$ 到 $k$，同时执行 $a_{s_{(i\bmod k)+1}} := a_{s_i}$。（也就是这些位置的值整体右移一格）
请你对每个 $i$（$1\le i\le n$），求出下标 $i$ **第一次**变为“好”（即第一次出现 $a_i=i$）的时刻（从 $0$ 秒开始计时）。
> 排列：由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的数组。
每经过 $1$ 秒钟，我们将所有不是“好”的下标对应的元素**整体向右轮转一位**。具体来说：
- 设 $s_1,s_2,\dots,s_k$ 是所有不是“好”的下标，按从小到大排列；
- 对于每个 $i$ 从 $1$ 到 $k$，同时执行 $a_{s_{(i\bmod k)+1}} := a_{s_i}$。（也就是这些位置的值整体右移一格）
请你对每个 $i$（$1\le i\le n$），求出下标 $i$ **第一次**变为“好”（即第一次出现 $a_i=i$）的时刻（从 $0$ 秒开始计时）。
> 排列：由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的数组。
输入格式
第一行一个整数 $t$（$1\le t\le 10^4$），表示测试用例数量。
每个测试用例：
- 第一行一个整数 $n$（$1\le n\le 10^6$）
- 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示一个排列（$1\le a_i\le n$）
保证所有测试用例中 $n$ 的总和不超过 $10^6$。
每个测试用例：
- 第一行一个整数 $n$（$1\le n\le 10^6$）
- 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示一个排列（$1\le a_i\le n$）
保证所有测试用例中 $n$ 的总和不超过 $10^6$。
输出格式
对每个测试用例，输出一行 $n$ 个整数，第 $i$ 个整数表示下标 $i$ 第一次变为“好”的时刻。
输入输出样例
输入 #1
2 5 3 2 4 1 5 6 2 1 4 6 5 3
输出 #1
1 0 1 1 0 2 1 2 1 0 1
说明/提示
样例解释
- 第一个用例里，$2$ 和 $5$ 一开始就满足 $a_2=2,a_5=5$，所以它们答案是 $0$；其余位置在第 $1$ 秒一起轮转后都变好。
- 第二个用例里，$5$ 一开始就是好下标；之后每秒对“不好”的下标集合轮转，分别在第 $1$ 秒、第 $2$ 秒让更多位置变好。
- 第一个用例里，$2$ 和 $5$ 一开始就满足 $a_2=2,a_5=5$，所以它们答案是 $0$；其余位置在第 $1$ 秒一起轮转后都变好。
- 第二个用例里，$5$ 一开始就是好下标；之后每秒对“不好”的下标集合轮转，分别在第 $1$ 秒、第 $2$ 秒让更多位置变好。