LG#P1440. 求 m 区间内的最小值

求 m 区间内的最小值

P1440 求m区间内的最小值

题目描述

\hspace{15pt}给定一个长度为 nn 的数列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},以及一个整数 mm。

\hspace{15pt}对于每个 i(1≦i≦n)i \left(1 \leqq i \leqq n\right),考虑 aia_i 之前(不含 aia_i)至多 mm 个数,即下标落在 [max⁡(1,i−m),i−1]\left[\max(1, i-m), i-1\right] 内的所有数,请求出这些数中的最小值。

\hspace{15pt}特别地,当 i=1i=1 时 a1a_1 之前没有任何数,此时答案为 00。

输入格式

\hspace{15pt}第一行输入两个整数 $n, m \left(1 \leqq m \leqq n \leqq 2 \times 10^6\right)$ 代表数列的长度和每次查看的区间长度上限。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 3 \times 10^7\right)$ 代表数列中的元素。

输出格式

\hspace{15pt}输出 nn 行,第 ii 行输出一个整数,代表下标区间 [max⁡(1,i−m),i−1]\left[\max(1, i-m), i-1\right] 内 aa 的最小值;特别地,第 11 行输出 00。

测试样例

6 2
7 8 1 4 3 2
0
7
7
1
1
3

样例 1 解释

\hspace{15pt}数列为 {7,8,1,4,3,2}\{7, 8, 1, 4, 3, 2\},m=2m=2,逐个下标计算如下:

∙ \hspace{23pt}\bullet\,当 i=1i=1 时,a1a_1 之前没有数,输出 00;

∙ \hspace{23pt}\bullet\,当 i=2i=2 时,区间 [1,1]\left[1, 1\right] 内只有 a1=7a_1=7,输出 77;

∙ \hspace{23pt}\bullet\,当 i=3i=3 时,区间 [1,2]\left[1, 2\right] 内的数为 7,87, 8,最小值为 77;

∙ \hspace{23pt}\bullet\,当 i=4i=4 时,区间 [2,3]\left[2, 3\right] 内的数为 8,18, 1,最小值为 11;

∙ \hspace{23pt}\bullet\,当 i=5i=5 时,区间 [3,4]\left[3, 4\right] 内的数为 1,41, 4,最小值为 11;

∙ \hspace{23pt}\bullet\,当 i=6i=6 时,区间 [4,5]\left[4, 5\right] 内的数为 4,34, 3,最小值为 33。

8 3
3 1 4 1 5 9 2 6
0
3
1
1
1
1
1
2