纯粹的单调队列练习题，用了一下，结果发现还不如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 ;

}