POJ 3264 Balanced Lineup 线段树 单点更新 求区间最值

//POJ 3264 Balanced Lineup 线段树 单点更新 求区间最值
/*
题意：
求区间最大值最小值之差

*/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define INF 100000000
#define N 50005
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r

int n,m;
int big,small;
int mmax[N<<2],mmin[N<<2];

int Max(int x,int y){
	return x>y?x:y;
}
int Min(int x,int y){
	return x<y?x:y;
}

void Pushup(int rt){
	mmax[rt] = Max(mmax[rt<<1],mmax[rt<<1|1]);
	mmin[rt] = Min(mmin[rt<<1],mmin[rt<<1|1]);
}

void Build(int rt,int l,int r){
	mmax[rt] = -1;
	mmin[rt] = INF;
	if(l == r)
		return;
	int mid = (l + r) >> 1;
	Build(lson);
	Build(rson);
}

void Update(int rt,int l,int r,int x,int val){
	if(l == r){
		mmax[rt] = Max(mmax[rt],val);
		mmin[rt] = Min(mmin[rt],val);
		return ;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) Update(lson,x,val);
	else		 Update(rson,x,val);
	Pushup(rt);
}

void Query(int rt,int l,int r,int L,int R){
	if(L <= l && R >= r){
		big = Max(big,mmax[rt]);
		small = Min(small,mmin[rt]);
		return;
	}
	int mid = (l + r) >> 1;
	if(L <= mid) Query(lson,L,R);
	if(R > mid ) Query(rson,L,R);
} 

int main(){
	int i,x;
	int a,b;
	while(scanf("%d %d",&n,&m)!=EOF){
		Build(1,1,n);
		for(i = 1; i <= n; ++i){
			scanf("%d",&x);
			Update(1,1,n,i,x);
		}	
		for(i = 1; i <= m; ++i){
			scanf("%d %d",&a,&b);
			big = -1;small = INF;
			Query(1,1,n,a,b);
			printf("%d\n",big-small);
		}
	}
	return 0;
}