poj 2823 滑动窗口 单调队列/线段树

题意：
求滑动窗口中的最大值和最小值。
分析：
可以用线段树来做，建完树后，查询区间n-k+1次就行，每次查询O(1)，时间复杂度O(n)
也可以用单调队列来做，比如求窗口中的最小值，那么就维护一个递增的队列，那么最小元素就是队首元素，每次右移，只要维护队列元素是递增的就可以。同样，求最大值，是维护一个递减的队列。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+9;
#define pos first
#define val second
#define mp make_pair
typedef pair<int,int>pii;
pii q[N];
int a[N];
int n,k;
void getmin()
{
    int l=1,r=0,i=0;
    for(;i<k;i++){
        while(r>=l&&q[r].val>a[i])r--;
        q[++r]=mp(i,a[i]);
    }
    printf("%d",q[l].val);
    for(;i<n;i++){
        if(q[l].pos<i-k+1)l++;
        while(r>=l&&q[r].val>a[i])r--;
        q[++r]=mp(i,a[i]);
        printf(" %d",q[l].val);
    }
    printf("
");
}
void getmax()
{
    int l=1,r=0,i=0;
    for(;i<k;i++){
        while(r>=l&&q[r].val<a[i])r--;
        q[++r]=mp(i,a[i]);
    }
    printf("%d",q[l].val);
    for(;i<n;i++){
        if(q[l].pos<i-k+1)l++;
        while(r>=l&&q[r].val<a[i])r--;
        q[++r]=mp(i,a[i]);
        printf(" %d",q[l].val);
    }
    printf("
");
}
int main()
{
    //freopen("f.txt","r",stdin);
    while(~scanf("%d%d",&n,&k)){
        for(int i=0;i<n;i++)scanf("%d",&a[i]);
        getmin();
        getmax();
    }
    return 0;
}