时限12s! 所以我用了线段树的黑暗做法，其实正解是用单调队列来做的。

//By SiriusRen#include 
     
      #include 
      
       #include 
       
        #define N 1000001#define lson l,mid,pos*2#define rson mid+1,r,pos*2+1using namespace std;int n,k,xx,yy,ansmax,ansmin,tree[N*4],MAX[N*4],MIN[N*4],ANSMAX[N],ANSMIN[N];void build(int l,int r,int pos){    if(l==r){scanf("%d",&tree[pos]);MAX[pos]=MIN[pos]=tree[pos];return;}    int mid=(l+r)/2;    build(lson),build(rson);    MAX[pos]=max(MAX[pos*2],MAX[pos*2+1]);    MIN[pos]=min(MIN[pos*2],MIN[pos*2+1]);}void query(int l,int r,int pos){    if(l>=xx&&r<=yy){ansmax=max(ansmax,MAX[pos]);ansmin=min(ansmin,MIN[pos]);return;}    int mid=(l+r)/2;    if(mid
        
         =yy)query(lson);    else query(lson),query(rson);}int main(){    scanf("%d%d",&n,&k);    build(1,n,1);    for(xx=1;xx<=n-k+1;xx++){        yy=xx+k-1,ansmax=-1*0x3fffffff,ansmin=0x3fffffff;        query(1,n,1),ANSMAX[xx]=ansmax,ANSMIN[xx]=ansmin;    }    for(xx=1;xx<=n-k+1;xx++)printf("%d ",ANSMIN[xx]);puts("");    for(xx=1;xx<=n-k+1;xx++)printf("%d ",ANSMAX[xx]);}
        
       
      
     

2016.11.16补坑 单调队列 （啊这题好水啊~）

//By SiriusRen#include 
     
      #include 
      
       using namespace std;int n,m,a[1000500];struct Node{
    int pos,weight;Node(){}Node(int x,int y){pos=x,weight=y;}}ans[1000500];deque
       
        maxx,minn;int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)scanf("%d",&a[i]);    for(int i=1;i<=n;i++){        if(!maxx.empty()&&maxx.front().pos+m<=i)maxx.pop_front();        if(!minn.empty()&&minn.front().pos+m<=i)minn.pop_front();        while(!maxx.empty()&&maxx.back().weight<=a[i])maxx.pop_back();        while(!minn.empty()&&minn.back().weight>=a[i])minn.pop_back();        maxx.push_back(Node(i,a[i]));minn.push_back(Node(i,a[i]));        ans[i].pos=maxx.front().weight,ans[i].weight=minn.front().weight;    }    for(int i=m;i<=n;i++)printf("%d ",ans[i].weight);putchar('\n');    for(int i=m;i<=n;i++)printf("%d ",ans[i].pos);}