#include"cstdio"
#include"cstring"
#include"algorithm"
using namespace std;
const int INF=0x7fffffff;
const int MAXN=1000005;
struct Node{
	int l,r;
	int min,max;
}a[MAXN*3];
int V,k;
void build(int l,int r,int n)
{
	a[n].l=l;
	a[n].r=r;
	if(l==r)
	{
		scanf("%d",&a[n].min);
		a[n].max=a[n].min;
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,n<<1);
	build(mid+1,r,(n<<1)|1);
	a[n].min=min(a[n<<1].min,a[(n<<1)|1].min);
	a[n].max=max(a[n<<1].max,a[(n<<1)|1].max);
}
int query(int l,int r,int n,int type)
{
	if(a[n].l==l&&a[n].r==r)
	{
		if(type==1)	return a[n].min;
		else	return a[n].max;
	}
	int mid=(a[n].l+a[n].r)>>1;
	if(r<=mid)	return query(l,r,n<<1,type);
	else if(mid<l)	return query(l,r,(n<<1)|1,type);
	else
	{
		if(type==1)	return min(query(l,mid,n<<1,type),query(mid+1,r,(n<<1)|1,type));
		else	return max(query(l,mid,n<<1,type),query(mid+1,r,(n<<1)|1,type));
	}
}
int main()
{
	while(scanf("%d%d",&V,&k)!=EOF)
    {
    	build(1,V,1);
    	for(int i=1;i<=V-k+1;i++)
    		printf("%d ",query(i,i+k-1,1,1));
    	printf("\n");
    	for(int i=1;i<=V-k+1;i++)	
    		printf("%d ",query(i,i+k-1,1,2));
    	printf("\n");
	}
	return 0;
}

• Re:线段树 (1316) 16310520330 2017-07-29 00:31:34