记录编号	445822	评测结果	WWAWAAWWW
题目名称	[POJ 2823]滑动窗口	最终得分	33
用户昵称	Ostmbh	是否通过	未通过
代码语言	C++	运行时间	1.852 s
提交时间	2017-09-06 20:43:30	内存使用	34.65 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1000000+20;
const int INF=0x7fffffff;
int a[MAXN];
int minn[MAXN*4],maxx[MAXN*4];
int n,k;

void build(int o,int l,int r){
	if(l==r) {
		minn[o]=a[l];
		maxx[o]=a[l];
	}
	else{
		int mid=(l+r)>>1;
		build(o*2,l,mid);
		build(o*2+1,mid+1,r);
		minn[o]=min(minn[o*2],minn[o*2+1]);
		maxx[o]=max(maxx[o*2],maxx[o*2+1]);
	}
}

int query_max(int o,int L,int R,int l,int r){
	if(L>R)return -INF;
	if(L>r||R<l) return -INF;
	if(l<=L&&R<=r) return maxx[o];
	else{
		int mid=(L+R)>>1;
		int temp1=-INF,temp2=-INF;
		if(mid>=l) temp1=query_max(o*2,L,mid,l,r);
		if(mid+1<=r) temp2=query_max(o*2+1,mid+1,R,l,r);
		return max(temp1,temp2);
	}
}

int query_min(int o,int L,int R,int l,int r){
	if(L>R)return INF;
	if(L>r||R<l) return INF;
	if(l<=L&&R<=r) return minn[o];
	else{
		int mid=(L+R)>>1;
		int temp1=INF,temp2=INF;
		if(mid>=l) temp1=query_min(o*2,L,mid,l,r);
		if(mid+1<=r) temp2=query_min(o*2+1,mid+1,R,l,r);
		return min(temp1,temp2);
	}
}


int main(){
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build(1,1,n);
	for(int i=0;i<=n-k;i++)printf("%d ",query_min(1,1,n,i,i+k));
	printf("\n");
	for(int i=0;i<=n-k;i++)printf("%d ",query_max(1,1,n,i,i+k));
	return 0;
}