求m区间内的最小值(Range Minimum in Window)

一个含有 $n$ 项的数列，求出每一项前的 $m$ 个数到它这个区间内的最小值。若前面的数不足 $m$ 项则从第 $1$ 个数开始，若前面没有数则输出 $0$ 。

第一行两个整数，分别表示 $n$ ， $m$ 。

第二行， $n$ 个正整数，为所给定的数列 $a_i$ 。

$n$ 行，每行一个整数，第 $i$ 个数为序列中 $a_i$ 之前 $m$ 个数的最小值。

6 2
7 8 1 4 3 2

对于 $100\%$ 的数据，保证 $1\le m\le n\le2\times10^6$ ， $1\le a_i\le3\times10^7$ 。

本题涉及的知识点从属于 CSP-J，难度（CF Rating）：1300。

Subtask	分值	测试点编号	说明
0	10	1	样例
1	20	2~7	小规模 n≤1000 / 边界 n=m=1 / m=n全局前缀最小值
2	15	8~11	Hack: 严格递增序列卡单调队列队首 / Hack: 严格递减序列频繁弹队尾 / Hack: n=2×10^6满规模
3	30	12~20	中大规模 n≤2×10^6 单调队列线性扫描压力
4	25	21~25	随机窗口长度与随机权值回归测试

出处：原题链接

#P1440. 求m区间内的最小值(Range Minimum in Window)