F - K inversions
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 100 点
問題文
(1, 2, \ldots, N) の順列 P = (P_1, P_2, \ldots, P_N) と整数 K が与えられます。
以下の疑似コードで表されるアルゴリズムを実行した場合、(1) の式は何回実行されますか?
for (int i = 1; i <= N; i++) { for (int j = 1; j <= N - i - K + 2; j++) { if ((P[j], P[j + 1], ..., P[j + K - 1]) が昇順に並んでいない) { (P[j], P[j + 1], ..., P[j + K - 1]) を昇順に並び替える ... (1) } } }
制約
- 入力は全て整数
- 2 \leq K \leq N \leq 2\times 10^5
- P は (1,2,\ldots,N) の順列
入力
入力は以下の形式で標準入力から与えられる。
N K P_1 P_2 \ldots P_N
出力
答えを 1 行に出力せよ。
入力例 1
4 2 1 3 4 2
出力例 1
2
(i, j) = (1, 1) のとき、(P_1, P_2) = (1, 3) で、(1) 式は実行されません。
(i, j) = (1, 2) のとき、(P_2, P_3) = (3, 4) で、(1) 式は実行されません。
(i, j) = (1, 3) のとき、(P_3, P_4) = (4, 2) で、(1) 式が実行され、(P_3, P_4) = (2, 4)に変化します。
(i, j) = (2, 1) のとき、(P_1, P_2) = (1, 3) で、(1) 式は実行されません。
(i, j) = (2, 2) のとき、(P_2, P_3) = (3, 2) で、(1) 式が実行され、(P_2, P_3) = (2, 3)に変化します。
(i, j) = (3, 1) のとき、(P_1, P_2) = (1, 2) で、(1) 式は実行されません。
全部で (1) 式が 2 回実行されたので、答えは 2 です。入力例 2
6 3 5 1 6 4 3 2
出力例 2
6
入力例 3
20 7 10 17 8 1 16 13 14 5 20 19 4 15 18 3 11 2 12 9 7 6
出力例 3
23