记录编号	437623	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	1.512 s
提交时间	2017-08-14 13:20:23	内存使用	91.87 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
	int sum(0),f(1);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar())
		if(ch=='-')
			f=-1;
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum*f;
}
struct node{
	int l,r,mx,mn;
	node *lch,*rch;
	node():l(0),r(0),mx(0),mn(0),lch(NULL),rch(NULL){}
}a[4000005],*root;
int n,k,cnt;
inline void pushup(node *rt){
	rt->mx=max(rt->lch->mx,rt->rch->mx);
	rt->mn=min(rt->lch->mn,rt->rch->mn);
}
inline void build(int l,int r,node *rt){
	rt->l=l,rt->r=r;
	if(l==r){
		rt->mx=rt->mn=read();
		return;
	}
	int mid((l+r)>>1);
	rt->lch=&a[++cnt],rt->rch=&a[++cnt];
	build(l,mid,rt->lch);
	build(mid+1,r,rt->rch);
	pushup(rt);
}
inline int query_mx(int l,int r,node *rt){
	if(l<=rt->l&&rt->r<=r)
		return rt->mx;
	int mid((rt->l+rt->r)>>1);
	int ret(-0x7fffffff);
	if(l<=mid)
		ret=max(ret,query_mx(l,r,rt->lch));
	if(mid<r)
		ret=max(ret,query_mx(l,r,rt->rch));
	return ret;
}
inline int query_mn(int l,int r,node *rt){
	if(l<=rt->l&&rt->r<=r)
		return rt->mn;
	int mid((rt->l+rt->r)>>1);
	int ret(0x7fffffff);
	if(l<=mid)
		ret=min(ret,query_mn(l,r,rt->lch));
	if(mid<r)
		ret=min(ret,query_mn(l,r,rt->rch));
	return ret;
}
inline int gg(){
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	n=read(),k=read();
	root=&a[++cnt];
	build(1,n,root);
	for(int i=1;i+k-1<=n;++i)
		printf("%d ",query_mn(i,i+k-1,root));
	putchar('\n');
	for(int i=1;i+k-1<=n;++i)
		printf("%d ",query_mx(i,i+k-1,root));
	return 0;
}
int K(gg());
int main(){;}