問題一覧 > 通常問題

No.3441 Sort Permutation 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 : 👑 potato167 / テスター : noya2
ProblemId : 13002 / yukicoder contest 492 (順位表) / 自分の提出
問題文最終更新日: 2026-02-05 18:13:32
yukicoder contest 492の他の問題:

問題文

正整数 $N$ と、$(1, 2, \dots, N)$ の順列 $P = (P_{1},P_{2},\dots,P_{N})$ が与えられます。

$k = 1, 2, \dots, N - 1$ について、以下の問いに答えてください。

Alice は以下の操作を繰り返し、$P$ を昇順ソートします。

  • $1$ 以上 $N$ 以下の整数 $i, j(i\neq j)$ を選び、$P_{i}$ と $P_{j}$ を入れ替える。このとき、$|i - j|$ が $k$ の倍数なら、Alice は $1$ ダメージ受ける。

Alice は最小の操作回数で $P$ を昇順ソートし、その上で受けるダメージを最小化する行動をします。

Alice が受けるダメージの和を求めてください。

制約

  • $2\leq N\leq 2\times 10^{5}$
  • $(P_{1}, P_{2},\dots,P_{N})$ は $(1,2,\dots,N)$ の順列
  • 入力は全て整数

入力

$N$
$P_{1}$ $P_{2}$ $\dots$ $P_{N}$

出力

$N - 1$ 行出力してください。

$i$ 行目には $k = i$ であるときの答えを出力してください。

サンプル

サンプル1
入力
6
6 4 5 2 3 1
出力
3
2
0
0
1

$k = 2$ のときの答えを考えます。

例えば以下のように $3$ 回操作をすると $P$ を昇順ソートできます。

  • $(i, j) = (2, 4)$ として操作する。操作後、$P = (6, 2, 5, 4, 3, 1)$ となる。
  • $(i, j) = (1, 6)$ として操作する。操作後、$P = (1, 2, 5, 4, 3, 6)$ となる。
  • $(i, j) = (3, 5)$ として操作する。操作後、$P = (1, 2, 3, 4, 5, 6)$ となる。

上記の $3$ 回の操作のうち、$1$ 回目と $3$ 回目の操作で Alice はそれぞれ $1$ ダメージ受けるため、Alice は合計 $2$ ダメージ受けます。

このように操作することが最小の操作回数で $P$ を昇順ソートし、その上で受けるダメージの和を最小化する行動のひとつであるため、$2$ 行目には $2$ を出力します。

サンプル2
入力
4
1 2 3 4
出力
0
0
0
サンプル3
入力
11
10 8 5 11 7 6 3 2 4 1 9
出力
6
3
2
0
0
1
0
0
1
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。