No.3441 Sort Permutation 2
Problem Statement
You are given a positive integer $N$ and a permutation $P = (P_{1},P_{2},\dots,P_{N})$ of $(1, 2, \dots, N)$.
For each of $k = 1, 2, \dots, N - 1$, answer the following question.
Alice sorts $P$ in ascending order by repeating the following operation.
- Choose integers $i, j(i\neq j)$ between $1$ and $N$, inclusive, and swap $P_{i}$ and $P_{j}$. If $|i - j|$ is a multiple of $k$, Alice takes $1$ damage.
Alice sorts $P$ in ascending order with the minimum number of operations and, subject to that, acts so as to minimize the damage she takes.
Find the total damage Alice takes.
Constraints
- $2\leq N\leq 2\times 10^{5}$
- $(P_{1}, P_{2},\dots,P_{N})$ is a permutation of $(1,2,\dots,N)$
- All input values are integers
Input
$N$
$P_{1}$ $P_{2}$ $\dots$ $P_{N}$
Output
Print $N - 1$ lines.
On the $i$-th line, print the answer for $k = i$.
Sample
Sample 1
Input
6 6 4 5 2 3 1
Output
3 2 0 0 1
Consider the answer for $k = 2$.
For example, $P$ can be sorted in ascending order with the following $3$ operations.
- Operate with $(i, j) = (2, 4)$. After the operation, $P = (6, 2, 5, 4, 3, 1)$.
- Operate with $(i, j) = (1, 6)$. After the operation, $P = (1, 2, 5, 4, 3, 6)$.
- Operate with $(i, j) = (3, 5)$. After the operation, $P = (1, 2, 3, 4, 5, 6)$.
Among the above $3$ operations, Alice takes $1$ damage on each of the $1$st and $3$rd operations, so she takes $2$ damage in total.
Operating in this way is one of the ways to sort $P$ in ascending order with the minimum number of operations while minimizing the total damage taken, so print $2$ on the $2$nd line.
Sample 2
Input
4 1 2 3 4
Output
0 0 0
Sample 3
Input
11 10 8 5 11 7 6 3 2 4 1 9
Output
6 3 2 0 0 1 0 0 1 0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2