这是一道题意简单，数据较大的题（喜闻乐见）；

一开始可能会想到RMQ问题，ST，线段树都是O(nlogn)，应该勉强能过（没试过）；

由于这道题区间是滚动连续的，所以，可以使用单调队列！

以最小值为例：

对于a[i],a[j],i>j;

如果a[i]<a[j],那么在加入i到滚动窗口中，找最小值一定不用考虑a[j];

因为a[j]比a[i]要先退出窗口，且即便i，j都在窗口中，那么a[j]一定不是最小值（a[i]<a[j]);

所以我们维护一个单调升序队列，对于新加入的元素，如果比队尾元素大，那么在队尾处入队（可能成为某个区间最小值）；

否则的话，找打一个合适的位置m使之前位置的树比它小，后面的数比它大，同时将位置m后面的数全部退队；

由于单调队列是随着下标递增的，那么对于滚动窗口滚出的元素，从队头判断即可。

1 var ans:array[0..1000000,1..2] of longint; 2     a,w:array[0..1000000] of longint; 3     h,f,r,mid,m,n,i,v:longint; 4 begin 5   readln(n,m); 6   for i:=1 to n do 7     read(a[i]); 8   a[0]:=-2147483647; 9   for i:=1 to n do10   begin11     if a[i]>a[w[h]] then12     begin13       h:=h+1;14       w[h]:=i;15     end16     else begin17       f:=1;18       r:=h;19       repeat20         mid:=(f+r) div 2;21         if (a[w[mid]]>=a[i]) and (a[w[mid-1]]
      
       =a[i]) then r:=mid-1 else f:=mid+1;23       until f>r;24       h:=mid;25       w[h]:=i;26     end;27     if i>=m then28     begin29       f:=1;30       r:=h;31       v:=0;32       repeat33         mid:=(f+r) div 2;34         if w[mid]
       
        =i-m+1 then36         begin37           v:=mid;38           r:=mid-1;39         end;40       until f>r;41       ans[i-m+1,1]:=a[w[v]];42     end;43   end;44   a[0]:=2147483647;45   h:=0;46   fillchar(w,sizeof(w),0);47   for i:=1 to n do48   begin49     if a[i]
        
         a[i]) then break;60         if (a[w[mid]]<=a[i]) then r:=mid-1 else f:=mid+1;61       until f>r;62       h:=mid;63       w[h]:=i;64     end;65     if i>=m then66     begin67       f:=1;68       r:=h;69       v:=0;70       repeat71         mid:=(f+r) div 2;72         if w[mid]
         
          =i-m+1 then74         begin75           v:=mid;76           r:=mid-1;77         end;78       until f>r;79       ans[i-m+1,2]:=a[w[v]];80     end;81   end;82   for i:=1 to n-m+1 do83     write(ans[i,1],' ');84   writeln;85   for i:=1 to n-m+1 do86     write(ans[i,2],' ');87   writeln;88 end.
         
        
       
      

单调队列，关键在于看出题目中的单调性；

还有单调队列一般存放标号比较方便