POJ2823.Sliding Window——单调队列

http://poj.org/problem?id=2823

求长度为k的子序列里面的最大值，最小值

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#define pk push_back
const int INF = 0x3f3f3f3f;
const int maxn = 1000010;
using namespace std;
int n,k;
int a[maxn],que[maxn];
vector<int> mx;
vector<int> mi;

void solve(vector<int>& dp)
{
    int front,rear;
    front=rear=1;
    dp.clear();
    for(int i=1;i<=n;++i){
        while(front<rear&&a[que[rear-1]]>a[i]) rear--;
        que[rear++]=i;
        while(front<rear&&i-que[front]+1>k) front++;
        if(i>=k) dp.pk(a[que[front]]);
    }
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // ONLINE_JUDGE
    while(scanf("%d%d",&n,&k)==2){
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        solve(mi);
        for(int i=1;i<=n;++i) a[i]=-a[i];
        solve(mx);
        for(int i=0;i<=n-k;++i){
            if(i<n-k) printf("%d ",mi[i]);
            else printf("%d\n",mi[i]);
        }
        for(int i=0;i<=n-k;++i){
            if(i<n-k) printf("%d ",-mx[i]);
            else printf("%d\n",-mx[i]);
        }
    }
    return 0;
}