Greedy Subsequences

题意翻译

定义一个序列的最长贪心严格上升子序列为：若选出的子序列为 $a$，对于其中相邻两项 $i,j$，不存在 $i < k < j$，满足在原序列 $b$ 中，有 $b_i < b_k$，换句话说就是选择一个元素后必须选择它之后第一个大于它的元素 给定一个长度为 $n$ 的序列，同时给定一个常数 $k$，求该序列的所有长度为 $k$ 的子区间的最长贪心严格上升子序列的长度 其中 $1 \le k \le n \le 10^6, 1 \le a_i \le n$

题目描述

For some array $ c $ , let's denote a greedy subsequence as a sequence of indices $ p_1 $ , $ p_2 $ , ..., $ p_l $ such that $ 1 \le p_1 < p_2 < \dots < p_l \le |c| $ , and for each $ i \in [1, l - 1] $ , $ p_{i + 1} $ is the minimum number such that $ p_{i + 1} > p_i $ and $ c[p_{i + 1}] > c[p_i] $ . You are given an array $ a_1, a_2, \dots, a_n $ . For each its subsegment of length $ k $ , calculate the length of its longest greedy subsequence.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 10^6 $ ) — the length of array $ a $ and the length of subsegments. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le n $ ) — array $ a $ .

输出格式

Print $ n - k + 1 $ integers — the maximum lengths of greedy subsequences of each subsegment having length $ k $ . The first number should correspond to subsegment $ a[1..k] $ , the second — to subsegment $ a[2..k + 1] $ , and so on.

输入输出样例

输入样例 #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 

说明

In the first example: - $ [1, 5, 2, 5] $ — the longest greedy subsequences are $ 1, 2 $ ( $ [c_1, c_2] = [1, 5] $ ) or $ 3, 4 $ ( $ [c_3, c_4] = [2, 5] $ ). - $ [5, 2, 5, 3] $ — the sequence is $ 2, 3 $ ( $ [c_2, c_3] = [2, 5] $ ). - $ [2, 5, 3, 6] $ — the sequence is $ 1, 2, 4 $ ( $ [c_1, c_2, c_4] = [2, 5, 6] $ ). In the second example: - $ [4, 5, 2, 5, 3, 6] $ — the longest greedy subsequences are $ 1, 2, 6 $ ( $ [c_1, c_2, c_6] = [4, 5, 6] $ ) or $ 3, 4, 6 $ ( $ [c_3, c_4, c_6] = [2, 5, 6] $ ). - $ [5, 2, 5, 3, 6, 6] $ — the subsequence is $ 2, 3, 5 $ ( $ [c_2, c_3, c_5] = [2, 5, 6] $ ).

题意翻译

定义一个序列的最长贪心严格上升子序列为：若选出的子序列为 $a$，对于其中相邻两项 $i,j$，不存在 $i < k < j$，满足在原序列 $b$ 中，有 $b_i < b_k$，换句话说就是选择一个元素后必须选择它之后第一个大于它的元素 给定一个长度为 $n$ 的序列，同时给定一个常数 $k$，求该序列的所有长度为 $k$ 的子区间的最长贪心严格上升子序列的长度 其中 $1 \le k \le n \le 10^6, 1 \le a_i \le n$