P1440 求m区间内的最小值
题目描述
给定一个长度为 n 的数列 {a1,a2,…,an},以及一个整数 m。
对于每个 i(1≦i≦n),考虑 ai 之前(不含 ai)至多 m 个数,即下标落在 [max(1,i−m),i−1] 内的所有数,请求出这些数中的最小值。
特别地,当 i=1 时 a1 之前没有任何数,此时答案为 0。
输入格式
第一行输入两个整数 $n, m \left(1 \leqq m \leqq n \leqq 2 \times 10^6\right)$ 代表数列的长度和每次查看的区间长度上限。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 3 \times 10^7\right)$ 代表数列中的元素。
输出格式
输出 n 行,第 i 行输出一个整数,代表下标区间 [max(1,i−m),i−1] 内 a 的最小值;特别地,第 1 行输出 0。
测试样例
6 2
7 8 1 4 3 2
0
7
7
1
1
3
样例 1 解释
数列为 {7,8,1,4,3,2},m=2,逐个下标计算如下:
∙当 i=1 时,a1 之前没有数,输出 0;
∙当 i=2 时,区间 [1,1] 内只有 a1=7,输出 7;
∙当 i=3 时,区间 [1,2] 内的数为 7,8,最小值为 7;
∙当 i=4 时,区间 [2,3] 内的数为 8,1,最小值为 1;
∙当 i=5 时,区间 [3,4] 内的数为 1,4,最小值为 1;
∙当 i=6 时,区间 [4,5] 内的数为 4,3,最小值为 3。
8 3
3 1 4 1 5 9 2 6
0
3
1
1
1
1
1
2