#P2251. 质量检测

    ID: 4965 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数学单调队列RMQst表,稀疏表

质量检测

题目描述

为了检测生产流水线上总共 NN 件产品的质量,我们首先给每一件产品打一个分数 AA 表示其品质,然后统计前 MM 件产品中质量最差的产品的分值 Q[m]=min{A1,A2,...Am}Q[m] = min\{A_1, A_2, ... A_m\},以及第 2 至第 M+1M + 1 件的 Q[m+1],Q[m+2]Q[m + 1], Q[m + 2] ... 最后统计第 NM+1N - M + 1 至第 NN 件的 Q[n]Q[n]。根据 QQ 再做进一步评估。

请你尽快求出 QQ 序列。

输入格式

输入共两行。

第一行共两个数 NNMM,由空格隔开。含义如前述。

第二行共 NN 个数,表示 NN 件产品的质量。

输出格式

输出共 NM+1N - M + 1 行。

第 1 至 NM+1N - M + 1 行每行一个数,第 ii 行的数 Q[i+M1]Q[i + M - 1]。含义如前述。

10 4
16 5 6 9 5 13 14 20 8 12

5
5
5
5
5
8
8

提示

[数据范围]

30%的数据,N1000N \le 1000

100%的数据,N100000N \le 100000

100%的数据,MN,A1000000M \le N, A \le 1 000 000