题目描述

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

输入输出格式

输入格式：

第一行两个数n，m。

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

输出格式：

n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。

输入样例#1：

6 2
7 8 1 4 3 2

输出样例#1：

0
7
7
1
1
3

说明
【数据规模】

m≤n≤2000000,ai ≤3×10 ^7

单调队列

#include<bits/stdc++.h>
using namespace std;
char buf[1<<17],*L=buf,*R=buf;
#define gc() L==R&&(R=(L=buf)+fread(buf,1,1<<17,stdin),L==R)?EOF:*L++;
template<typename T>
inline void read(T&x) {
    int flag=x=0;
    char ch=gc();
    while (ch<'0'||ch>'9')
        flag|=ch=='-',ch=gc();
    while (ch>='0'&&ch<='9')
        x=(x<<3)+(x<<1)+ch-48,ch=gc();
    if(flag)
        x=-x;
}
const int MAXN=1e5+10;
int n,m,ans[MAXN];
struct Node{
    int num,val;
}x;
deque<Node>que;
int main() {
    freopen("in.txt","r",stdin);
    read(n),read(m);
    for(int i=1;i<n;++i){
        read(x.val);
        x.num=i;
        //当前val就是该区间最后一个数，如果他前面的都比他大，都弹出
        while(!que.empty()&&que.back().val>x.val)que.pop_back();
        que.push_back(x);//压入
        //从队头弹出不在区间里的数
        while(!que.empty()&&que.front().num<=i-m)que.pop_front();
        ans[i]=que.front().val;
    }
    for(int i=0;i<n;++i){
        printf("%d\n",ans[i]);
    }
    return 0;
}