#include<stdio.h>
#include<malloc.h>
int max(int x,int y)
{
	return x>y?x:y;
}
int min(int x,int y)
{
	return x<y?x:y;
}
struct node
{
	int min,max;
}tree[200001];
int a[50005],n;
void build(int x,int l,int r)
{
	if(l==r)
	{
		tree[x].max=tree[x].min=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build((x<<1)+1,mid+1,r);
	tree[x].max=max(tree[x<<1].max,tree[(x<<1)+1].max);
	tree[x].min=min(tree[x<<1].min,tree[(x<<1)+1].min);
	return ;
}
int nowmin;
int nowmax;
void getans(int x,int l,int r,int head,int end)
{
	if(l==head&&end==r)
	{
		nowmin=min(tree[x].min,nowmin);
		nowmax=max(tree[x].max,nowmax);
		return ;
	}
	int mid=(head+end)>>1;
	if(l<=mid) 
		getans(x<<1,l,min(mid,r),head,mid);
	if(r>mid) 
		getans((x<<1)+1,max(mid+1,l),r,mid+1,end);
}
int main()
{
	int m,i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
		scanf("%d",a+i);
	a[n+1]=-(1<<30);
	a[0]=1<<30;
	build(1,1,n);
	while(m--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		nowmax=-(1<<30);
		nowmin=1<<30;
		getans(1,x,y,1,n);
		printf("%d\n",nowmax-nowmin);
	}
	return 0;
}

• 不好意思是线段树哈 激动了 (0) 20055106 2007-09-24 20:43:30
• Re:感觉你的程序有问题…… (49) LittleKid 2007-09-30 11:36:19
  • Re:感觉你的程序有问题…… (80) LittleKid 2007-09-30 11:39:11