记录编号	21697	评测结果	AAAAAAAAA
题目名称	495.[POJ 2823]滑动窗口	最终得分	100
用户昵称	Pom	是否通过	通过
代码语言	C++	运行时间	2.543 s
提交时间	2010-11-12 19:29:39	内存使用	53.68 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN=1000222;

int n,m,i,j,k,ps=0,ans1[MAXN],ans2[MAXN],x,y;

struct xds
{
	int da,xiao,l,r;
	xds *cl,*cr;
}T[MAXN*2],*root=T;

void mkt(int l,int r,xds *p)
{
	p->l=l;
	p->r=r;
	int mid=(l+r)>>1;
	if (r>l)
	{
		++ps;
		p->cl=T+ps;
		mkt(l,mid,p->cl);
		++ps;
		p->cr=T+ps;
		mkt(mid+1,r,p->cr);
		p->xiao=min(p->cl->xiao,p->cr->xiao);
		p->da=max(p->cl->da,p->cr->da);
	}
	else 
	{
		scanf("%d",&mid);
		p->da=p->xiao=mid;
	}
}

void init()
{
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	scanf("%d%d",&n,&m);
	mkt(1,n,root);
}

void cha(xds *p)
{
	if (p->l>y || p->r<x) return;
	if (p->l>=x && p->r<=y)
	{
		if (p->xiao<ans1[i]) ans1[i]=p->xiao;
		if (p->da>ans2[i]) ans2[i]=p->da;
	}
	else
	{
		cha(p->cl);
		cha(p->cr);
	}
}

void solve()
{
	for (i=1;i<=n-m+1;i++)
	{
		ans1[i]=2000000000;
		ans2[i]=-ans1[i];
		x=i;
		y=i+m-1;
		cha(root);
	}
	for (i=1;i<n-m+1;i++)
		printf("%d ",ans1[i]);
	printf("%d\n",ans1[n-m+1]);
	for (i=1;i<n-m+1;i++)
		printf("%d ",ans2[i]);
	printf("%d\n",ans2[n-m+1]);
}

int main()
{
	init();
	solve();
	return 0;
}