POJ3264，Balanced Lineup（線段樹區間查詢最值）

這道題也是線段樹的裸題，但其實也沒有必要用線段樹來做，可以用RMQ等其它區間查詢最值的方式，用線段樹反而會更慢，不過作為線段樹的入門題，拿來練練手也是挺不錯的。

線段樹AC代碼如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=5e4+6;
const int inf=0x3f3f3f3f;
int h[maxn];
struct Node
{
	int l,r;
	int max_,min_;
}tr[maxn<<2];

void push_up(int rt)
{
	tr[rt].max_=max(tr[rt<<1].max_,tr[rt<<1|1].max_);
	tr[rt].min_=min(tr[rt<<1].min_,tr[rt<<1|1].min_);
}

void build(int rt,int l,int r)
{
	tr[rt].l=l;	tr[rt].r=r;
	if(tr[rt].l==tr[rt].r)
	{
		tr[rt].max_=h[l];
		tr[rt].min_=h[l];
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	push_up(rt);
}

void query(int rt,int l,int r,int &ma,int &mi)
{
	if(l<=tr[rt].l&&tr[rt].r<=r)
	{
		ma=max(ma,tr[rt].max_);
		mi=min(mi,tr[rt].min_);
		return;
	}
	if(tr[rt].l==tr[rt].r)	return;
	int mid=(tr[rt].l+tr[rt].r)>>1;
	if(mid<l)	query(rt<<1|1,l,r,ma,mi);
	else if(mid>=r)	query(rt<<1,l,r,ma,mi);
	else
	{
		query(rt<<1,l,mid,ma,mi);
		query(rt<<1|1,mid+1,r,ma,mi);
	}
}

int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i)
		scanf("%d",&h[i]);
	build(1,1,n);
	while(q--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		int mi=inf,ma=-inf;
		query(1,a,b,ma,mi);
		printf("%d\n",ma-mi);
	}
	return 0;
}