← 返回题目列表

AtCoder · utpc2022_f

F. K 反演

中文机器翻译题面 查看原题

配点 : 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