<span>POJ2823 Sliding Window（单调队列模版题）</span>

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
#define M 1000005
int n,k,a[M],n1[M],n2[M];
void init()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
}
void makemin()
{
    int head=0,end=0;
    for(int i=0;i<k;i++)
    {
        while(end>head&&a[i]<=n1[end-1])
            end--;
        n1[end]=a[i];
        n2[end]=i;
        end++;
    }
    for(int i=k;i<n;i++)
    {
        printf("%d ",n1[head]);
        while(head<end&&n2[head]<=i-k)
            head++;
        while(end>head&&a[i]<=n1[end-1])
            end--;
        n1[end]=a[i];
        n2[end]=i;
        end++;
    }
    printf("%d\n",n1[head]);
}
void makemax()
{
    int head=0,end=0;
    for(int i=0;i<k;i++)
    {
        while(end>head&&a[i]>=n1[end-1])
            end--;
        n1[end]=a[i];
        n2[end]=i;
        end++;
    }
    for(int i=k;i<n;i++)
    {
        printf("%d ",n1[head]);
        while(head<end&&n2[head]<=i-k)
            head++;
        while(end>head&&a[i]>=n1[end-1])
            end--;
        n1[end]=a[i];
        n2[end]=i;
        end++;
    }
    printf("%d\n",n1[head]);
}
int main()
{
    //freopen("in.txt","r",stdin);
    init();
    makemin();
    makemax();
    return 0;
}