AT_utpc2022_f.K inversions

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个 $ (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)
        }
    }
}

输入格式

输入从标准输入中给出，格式如下：

$ N $ $ K $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

输出格式

输出式 (1) 被执行的次数，输出一行即可。

输入输出样例

输入#1
```
4 2
1 3 4 2
```
输出#1
```
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

说明/提示

样例解释 1

当 $ (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 \leq K \leq N \leq 2\times 10^5 $
$ P $ 为 $ (1,2,\ldots,N) $ 的一个排列。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页