poj 2823 Sliding Window (单调队列)

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

纯粹的单调队列练习题，用了一下输入的加速，结果发现还不如scanf快...

话说前段时间搞单调优化的时候，就是有点卡在单调队列上了，当时真没整明白资料里说的到底在维护什么...今天费老传了DP资料(完整版...)才算真搞懂。唉，浪费了那么多激情... 

为DP的单调优化做准备吧，明天开始搞DP了，不能再缩了... 

code:

#include<cstdio>
int data[1000005] ;
int queue[1000005] ;
int n, k ;
void getMin(){
    int h, r ;
    h = r = 0 ;
    queue[0] = 0 ;
    for(int i=0; i<n; i++){
        if(i-queue[h]==k)   h ++ ;
        if(r==h-1||data[i]>data[queue[r]]){
            r ++ ;
            queue[r] = i ;
        }
        else{
            while(r>=h&&data[i]<=data[queue[r]]){
                queue[r] = i ;
                r -- ;
            }
            r ++ ;
        }
        if(i>=k-1)    printf("%d ", data[queue[h]]) ;
    }
    printf("\n") ;
}
void getMax(){
    int h, r ;
    h = r = 0 ;
    queue[0] = 0 ;
    for(int i=0; i<n; i++){
        if(i-queue[h]==k)   h ++ ;
        if(r==h-1||data[i]<data[queue[r]]){
            r ++ ;
            queue[r] = i ;
        }
        else{
            while(r>=h&&data[i]>=data[queue[r]]){
                queue[r] = i ;
                r -- ;
            }
            r ++ ;
        }
        if(i>=k-1)    printf("%d ", data[queue[h]]) ;
    }
    printf("\n") ;
}
int main(){
    while(~scanf("%d%d", &n, &k)){
        for(int i=0; i<n; i++)
            scanf("%d", &data[i]) ;
        getMin() ;
        getMax() ;
    }
    return 0 ;
}