Description
给你一个长度为N的数组，一个长为K的滑动的窗体从最左移至最右端，你只能见到窗口的K个数，每次窗体向右移动一位，如下表：
你的任务是找出窗口在各位置时的max value , min value．
Input
第一行n，k，第二行为长度为n的数组
Output
第一行每个位置的min value,第二行每个位置的max value
Sample Input
8 3
1 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3
3 3 5 5 6 7
Hint
20％：n≤500；
50％：n≤100000；
100％：n≤1000000；
刷刷水题补个欠账
两个单调队列.
// It is made by XZZ
// Fei Fan Ya Xi Lie~~~
#include<cstdio>
#include<algorithm>
using namespace std;
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int maxn=1e6+1;
class deque{
private:
int T[maxn],p[maxn];
int hd,tl;
public:
deque(){hd=tl=0;}
il vd push(int&num,int&pos){T[tl]=num,p[tl]=pos,++tl;}
il vd pop_l(){++hd;}
il vd pop_r(){--tl;}
il bool notempty(){return hd^tl;}
il const int&back(){return T[tl-1];}
il const int&front_p(){return p[hd];}
il const int&front_n(){return T[hd];}
il vd print(){
for(rg int i=hd;i^tl;++i)printf("%d ",T[i]);puts("");
for(rg int i=hd;i^tl;++i)printf("%d ",p[i]);puts("");puts("");
}
};
deque A,B;
int Min[maxn],Max[maxn];
int main(){
// freopen("2284.in","r",stdin);
// freopen("2284.out","w",stdout);
int n=gi(),k=gi(),a;
for(rg int i=1;i<k;++i){
a=gi();
while(A.notempty()&&A.back()<=a)A.pop_r();
A.push(a,i);
while(B.notempty()&&B.back()>=a)B.pop_r();
B.push(a,i);
}
int l=1,r=k,cnt=0;
while(r<=n){
a=gi();
while(A.notempty()&&A.front_p()<l)A.pop_l();
while(A.notempty()&&A.back()<=a)A.pop_r();
A.push(a,r);
while(B.notempty()&&B.front_p()<l)B.pop_l();
while(B.notempty()&&B.back()>=a)B.pop_r();
B.push(a,r);
++cnt,Min[cnt]=A.front_n(),Max[cnt]=B.front_n();
++l,++r;
}
for(rg int i=1;i<=cnt;++i)printf("%d ",Max[i]);puts("");
for(rg int i=1;i<=cnt;++i)printf("%d ",Min[i]);puts("");
return 0;
}