#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
struct TREE 
{
    int l, r, p;
	int min,max;
}tree[4*1000000];
int data[1000005];
void build(int l, int r, int p)
{
	tree[p].l=l;
	tree[p].r=r;
	if(l==r)
	{
		tree[p].min=tree[p].max=data[l];
		return ;
	}
	int mid = (l+r)>>1;
    build(l, mid, 2*p);
    build(mid + 1, r, 2*p+1);
	tree[p].min=min(tree[2*p].min,tree[2*p+1].min);
	tree[p].max=max(tree[2*p].max,tree[2*p+1].max);
}
int minl[1000005],maxl[1000005];
void query(int l,int r,int& min,int& max,int p)
{
	if(tree[p].l == l && tree[p].r == r)
	{
		min = tree[p].min;
		max = tree[p].max;
		return ;
	}
	int mid = (tree[p].l + tree[p].r)>>1;
	if(mid >= r)
		query(l,r,min,max,p*2);
	else if(mid<l)
		query(l,r,min,max,p*2+1);
	else 
	{
		int max2,min2;
		query(l,mid,min,max,p*2);
		query(mid+1,r,min2,max2,p*2+1);
		min=min<min2?min:min2;
		max=max>max2?max:max2;
	}
}
int main()
{
	int n,k;
	int i;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		for(i=1;i<=n;i++)
			scanf("%d",&data[i]);
		build(1,n,1);
		int maxt,mint;
		for(i=1;i<=n-k+1;i++)
		{
			query(i,i+k-1,mint,maxt,1);
			minl[i]=mint;
			maxl[i]=maxt;
		}
		for(i=1;i<=n-k;i++)
			printf("%d ",minl[i]);
		printf("%d\n",minl[i]);
		for(i=1;i<=n-k;i++)
			printf("%d ",maxl[i]);
		printf("%d\n",maxl[i]);
	}
	return 0;
}

• Re:请教大牛，我初学这个线段数，我的代码怎么wa掉了 (1553) skogt 2010-10-28 10:30:21