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] $ ).