luogu P1440 求m区间内的最小值 | 单调队列

luogu P1440 求m区间内的最小值

单调队列：元素只能从队首与队尾操作

时间复杂度O(n)

维护出的队伍是查询范围内的而且是递增的，所以队头必定是查询区域内的最小值

#include<deque> //头文件 
deque <int> q;    
q.pop_back();   //弹出队尾元素 
q.pop_front();  //弹出队首元素 
q.push_back(x); //将 x 放入队尾 
q.push_front(y);//将 y 放入队首 
q.front();      //访问队首元素 
q.back();       //访问队尾元素 
q.clear();      //清空队列 

#include<cstdio>
#include<deque>
using namespace std;
struct ll
{
    int x,v;
}a[2000010];
deque<ll> q;
int n,m;
int main()
{
    ll now,k;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].v);
        a[i].x=i;
    }
    printf("0
");
    for(int i=2;i<=n;i++)
    {
        while(!q.empty()&&q.back().v>=a[i-1].v) q.pop_back();
        q.push_back(a[i-1]);
        while(q.front().x<=i-m-1) q.pop_front();
        printf("%d
",q.front().v);
    }
    return 0;
}