CF1132G Greedy Subsequences

对于某个数组 $c$，我们定义“贪心子序列”为一组下标序列 $p_1, p_2, \dots, 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, 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]$）。 由 ChatGPT 4.1 翻译