← 返回题目列表

Codeforces · 1132/G

G. 贪婪子序列

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

对于某些数组 $$$c$$$,让我们将贪婪子序列表示为索引序列 $$$p_1$$$, $$$p_2$$$, ..., $$$p_l$$$ 使得 $$$1 \le p_1 < p_2 < \dots < p_l \le |c|$$$,并且对于每个 $$$i \in [1, l - 1]$$$,$$$p_{i + 1}$$$ 是满足 $$$p_{i + 1} > p_i$$$ 且 $$$c[p_{i + 1}] > c[p_i]$$$ 的最小数。

给你一个数组 $$$a_1, a_2, \dots, a_n$$$。对于长度 $$$k$$$ 的每个子段,计算其最长贪婪子序列的长度。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 10^6$$$) — 数组 $$$a$$$ 的长度和子段的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — 数组 $$$a$$$。

输出

打印 $$$n - k + 1$$$ 整数 — 每个长度为 $$$k$$$ 的子段的贪婪子序列的最大长度。第一个数字应对应于子分段 $$$a[1..k]$$$,第二个数字应对应于子分段 $$$a[2..k + 1]$$$,依此类推。

示例

输入 #1

6 4
1 5 2 5 3 6

输出 #1

2 2 3

输入 #2

7 6
4 5 2 5 3 6 6

输出 #2

3 3

注意

在第一个示例中:

- $$$[1, 5, 2, 5]$$$ — 最长的贪婪子序列是 $$$1, 2$$$ ($$$[c_1, c_2] = [1, 5]$$$) 或 $$$3, 4$$$ ($$$[c_3, c_4] = [2, 5]$$$)。
- $$$[5, 2, 5, 3]$$$ — 序列为 $$$2, 3$$$ ($$$[c_2, c_3] = [2, 5]$$$)。
- $$$[2, 5, 3, 6]$$$ — 序列为 $$$1, 2, 4$$$ ($$$[c_1, c_2, c_4] = [2, 5, 6]$$$)。

在第二个示例中:

- $$$[4, 5, 2, 5, 3, 6]$$$ — 最长贪婪子序列为 $$$1, 2, 6$$$ ($$$[c_1, c_2, c_6] = [4, 5, 6]$$$) 或 $$$3, 4, 6$$$ ($$$[c_3, c_4, c_6] = [2, 5, 6]$$$)。
- $$$[5, 2, 5, 3, 6, 6]$$$ — 子序列是 $$$2, 3, 5$$$ ($$$[c_2, c_3, c_5] = [2, 5, 6]$$$)。