Sliding Window poj 单一队列的简单应用

Sliding Window poj 单调队列的简单应用

/*算是单调队列入门吧。简单。根据ppt模板易得答案。*/
#include <iostream>
#include <stdio.h>
#define maxn 1000001
using namespace std;
struct node
{
    int num,id;
    node(){}
    node(int _num,int _id)
    {
        num=_num;
        id=_id;
    }
}q[maxn];
node p[maxn];
int a[maxn];
int mmax[maxn];
int mmin[maxn];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int t=0,f=0;
    int head=0,rear=0;
    int h=0,r=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        while(head<rear&&q[rear-1].num<a[i]) rear--;
        q[rear++]=node(a[i],i);
        while(head<rear&&i-q[head].id>=k) head++;
        mmax[t++]=q[head].num;
        while(h<r&&p[r-1].num>a[i]) r--;
        p[r++]=node(a[i],i);
        while(h<r&&i-p[h].id>=k) h++;
        mmin[f++]=p[h].num;
    }
    printf("%d",mmin[k-1]);
    for(int i=k;i<t;i++)
    printf(" %d",mmin[i]);
    printf("\n");
    printf("%d",mmax[k-1]);
    for(int i=k;i<f;i++)
    printf(" %d",mmax[i]);
    printf("\n");
    return 0;
}