此题的较好方法为单调队列。稍后实现一下。用阉割的线段树来写9600ms++囧~
简单的线段树就不说了，详情可以看以前的文章或者下面的代码.....
虽然有点凑数量之嫌....
#include<iostream>
#define MAXN 1000001
using namespace std;int _max[MAXN<<2];
int _min[MAXN<<2];int mx( int a,int b ){return a>b?a:b;
}
int mn( int a,int b ){return a<b?a:b;
}void PushUp( int rt )
{_max[rt]=mx( _max[rt<<1],_max[rt<<1|1] );_min[rt]=mn( _min[rt<<1],_min[rt<<1|1] );
}void build(int l,int r,int rt)
{if( l==r ){scanf( "%d",&_max[rt] );_min[rt]=_max[rt];return ;}int m=(l+r)>>1;build( l,m,rt<<1 );build( m+1,r,rt<<1|1 );PushUp(rt);
}int query( int l,int r,int c,int L,int R,int rt )
{if( l<=L&&R<=r ){if( c )return _max[rt];elsereturn _min[rt];}int m=(L+R)>>1;int res;if( c ){ res=-214748363;if( l<=m ) res=mx(res,query( l,r,c,L,m,rt<<1) );if( m<r ) res=mx( res,query( l,r,c,m+1,R,rt<<1|1) );return res;}else{res=214748363;//res=100;if( l<=m ) res=mn(res,query( l,r,c,L,m,rt<<1) );if( m<r ) res=mn( res,query( l,r,c,m+1,R,rt<<1|1) );return res;}
}int main()
{int n,c,i;while( scanf( "%d %d",&n,&c)!=EOF ){build(1,n,1);printf( "%d",query( 1,c,0,1,n,1 ) );for( i=2;;i++ ){if( i+c-1<=n ){printf( " %d",query( i,i+c-1,0,1,n,1 ) );}elsebreak;}printf( "\n%d",query( 1,c,1,1,n,1 ) );for( i=2;;i++ ){if( i+c-1<=n ){printf( " %d",query( i,i+c-1,1,1,n,1 ) );}elsebreak;}printf( "\n" );}return 0;
}