poj 3264

线段树入门题

#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
const int maxn=50000;
const int inf=1<<30;
int n,q;
int minv[maxn*3],maxv[maxn*3];
void init()
{
	for(int i=0;i<maxn*3;i++)
	{
		minv[i]=inf;
		maxv[i]=-1;
	}
}
void update(int no,int p,int l,int r,int v)
{
	if(l==r) minv[no]=maxv[no]=v;
	else 
	{
		int m=l+(r-l)/2;
		if(p<=m) update(no*2,p,l,m,v);
		else update(no*2+1,p,m+1,r,v);
		minv[no]=minv[no*2]<minv[no*2+1]?minv[no*2]:minv[no*2+1];
		maxv[no]=maxv[no*2]>maxv[no*2+1]?maxv[no*2]:maxv[no*2+1];
	}
}
int tmax,tmin,ql,qr;
void query(int no,int l,int r)
{
	if(l>=ql&&r<=qr)
	{
		if(maxv[no]>tmax) tmax=maxv[no];
		if(minv[no]<tmin) tmin=minv[no];
	}
	else
	{
		int m=l+(r-l)/2;
		if(ql<=m) query(no*2,l,m);
		if(qr>m) query(no*2+1,m+1,r);
	}
}	
int main()
{
	while(~scanf("%d%d",&n,&q))
	{
		init();
		int i,j;
		int v;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&v);
			update(1,i,1,maxn,v);
		}
		for(i=0;i<q;i++)
		{
			tmax=-1;tmin=inf;
			scanf("%d%d",&ql,&qr);
			query(1,1,maxn);
			printf("%d\n",tmax-tmin);
		}	
	}
	return 0;			
}