poj 32643(線分樹)

Balanced Lineup
Time Limit:5000 MS
 
メモリLimit:65536 K
Total Submissions:27962
 
Acceepted:131336
Case Time Limit:2000 MS
Description
For the daily milking,Farmer John's N cows(1≦N≦50,000)alwaysラインナップup in the same order.One dame Farmer John decides to organize of the cows.To keep the game the fine ingnes.ings.ingline.for all the cows to have fun they shound not differ too much in height.
Farmer John has made a list of Q(1≦Q≦200,000)potental groups of cows and their height(1≦height≦1,000,000,000).For each group,he wants your help to determine the difference in height the the est the
Input
Line 1:Two space-separated integers、
N and
Q.
Lines 2.
N+1:Line
i＋1 contains a single integer that is the height of cow
i
リンス
N+2.
N＋
Q+1:Two integers
A and
B(1≦
A≦
B≦
N)representing the range of cows from
A to
B inclusive.
Output
Lines 1.
Q:Each LINE contains a single integer that is a reponse to a reply and indicates the difference in height between the tallest and shotest cow in the range.
Sample Input

6 3
1
7
3
4
2
5
1 5
4 6
2 2

Sample Output

6
3
0

#include <iostream>
#include<cstdio> 
#include <algorithm> 
#include <numeric>
using namespace std; 
#define MY_MIN 99999999 
#define MY_MAX -99999999 
struct CNode 
{
	int L,R;
	int nMin,nMax; 
	CNode * pLeft, * pRight;
};
int nMax, nMin;
CNode Tree[1000000];//           +1   
int nCount = 0; ////     

void BuildTree(CNode * pRoot, int L,int R) 
{ 
	pRoot->L = L;
	pRoot->R = R; 
	pRoot->nMin = MY_MIN; 
	pRoot->nMax = MY_MAX; 
	if ( L != R) 
	{
		nCount ++; 
		pRoot->pLeft = Tree + nCount; 
		nCount ++; 
		pRoot->pRight = Tree + nCount; 
		BuildTree( pRoot->pLeft, L, ( L + R )/2);
		BuildTree( pRoot->pRight, (L + R) / 2 + 1,R); 
	} 
}

void Insert( CNode * pRoot , int i,int v) 
//  i  ，   v，     
{ 
	if( pRoot->L == i && pRoot->R == i ) 
	{
		pRoot->nMin = pRoot->nMax = v; 
		return; 
	} 
	pRoot->nMin = min(pRoot->nMin,v);
	pRoot->nMax =max(pRoot->nMax,v); 
	if( i <= (pRoot->L + pRoot->R )/2 ) 
		Insert( pRoot->pLeft,i,v); 
	else Insert( pRoot->pRight,i,v);
}

void Query(CNode * pRoot, int s, int e) 
//    [s,e]         ，            
{
	if( pRoot->nMin >= nMin && pRoot->nMax <= nMax ) 
		return;
	if( s == pRoot->L && e == pRoot->R)
	{ 
		nMin = min(pRoot->nMin,nMin); 
		nMax =max(pRoot->nMax,nMax); 
		return ; 
	} 
	if( e <= (pRoot->L + pRoot->R) / 2 ) 
		Query(pRoot->pLeft, s,e);
	else if( s >= (pRoot->L + pRoot->R) / 2 + 1) 
		Query(pRoot->pRight, s,e); 
	else
	{ 
		Query(pRoot->pLeft, s,(pRoot->L + pRoot->R) / 2);
		Query(pRoot->pRight, (pRoot->L + pRoot->R) / 2+1 ,e); 
	} 
}

int main() 
{
	int n,q,h;
	int i,j,k; 
	scanf("%d%d",&n,&q); 
	nCount = 0; 
	BuildTree(Tree,1,n);
	for( i = 1;i <= n;i ++ ) 
	{ 
		scanf("%d",&h);
		Insert( Tree,i,h);
	} 
	for( i = 0;i < q;i ++ ) 
	{ 
		int s,e; scanf("%d%d", &s,&e); 
		nMax = MY_MAX;
		nMin = MY_MIN; 
		Query(Tree,s,e);
		printf("%d
",nMax - nMin); 
	} 
	return 0;
}