思路：

　　单调队列；

　　以前遇到都是用线段树水过；

　　现在为了优化dp不得不学习单调队列了；

 

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define maxn 1000005struct QueueType {    int x,dis;};struct QueueType mique[maxn],maque[maxn],ai[maxn];int n,k,mihead,mitail=-1,mahead,matail=-1;inline void in(int &now){    int if_z=1;now=0;    char Cget=getchar();    while(Cget>'9'||Cget<'0')    {        if(Cget=='-') if_z=-1;        Cget=getchar();    }    while(Cget>='0'&&Cget<='9')    {        now=now*10+Cget-'0';        Cget=getchar();    }    now*=if_z;}int main(){    in(n),in(k);    for(int i=1;i<=n;i++) in(ai[i].dis),ai[i].x=i;    for(int i=1;i
         
          mihead)        {            if(mique[mitail].dis<=mique[mitail-1].dis) mique[mitail-1]=mique[mitail--];            else break;        }        maque[++matail]=ai[i];        while(matail>mahead)        {            if(maque[matail].dis>=maque[matail-1].dis) maque[matail-1]=maque[matail--];            else break;        }    }    for(int i=k;i<=n;i++)    {        mique[++mitail]=ai[i];        while(mitail>mihead)        {            if(mique[mitail].dis<=mique[mitail-1].dis) mique[mitail-1]=mique[mitail--];            else break;        }        printf("%d ",mique[mihead].dis);        if(mique[mihead].x==i-k+1) mihead++;    }    printf("\n");    for(int i=k;i<=n;i++)    {        maque[++matail]=ai[i];        while(matail>mahead)        {            if(maque[matail].dis>=maque[matail-1].dis) maque[matail-1]=maque[matail--];            else break;        }        printf("%d ",maque[mahead].dis);        if(maque[mahead].x==i-k+1) mahead++;    }    return 0;}