A6910 | $排列轮转排序$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个长度为 $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$ 个互不相同的整数组成的数组。

第一行一个整数 $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$ 个整数，第 $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

C++ 编辑器

输入

输出