#include <iostream>
#include <cstdio>
#include <algorithm>
const int MY_MAX = -99999999;
const int MY_MIN = 99999999;
using namespace std;
struct CNode
{
int R, L;
int nMax, nMin;
CNode * pLeft, * pRight;
}Tree[1000000];
//CNode Tree[1000000];
int nMax, nMin;
int nCount = 0;
void BuildTree( CNode * pRoot, int L, int R )
{
pRoot->L = L;
pRoot->R = R;
pRoot->nMax = MY_MAX;
pRoot->nMin = MY_MIN;
if( R != L )
{
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 )
{
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 )
{
if( pRoot->nMax <= nMax && pRoot->nMin >= nMin )
return ;
if( s == pRoot->L && e == pRoot->R )
{
nMax = max(pRoot->nMax, nMax);
nMin = min(pRoot->nMin,nMin);
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, s, e;
int h;
scanf("%d%d", &n, &q);
nCount = 0;
BuildTree( Tree, 1, n);
for( int i = 1; i <= n; i++ )
{
scanf("%d", &h);
Insert( Tree, i, h );
}
for( int i = 0; i < q; i++)
{
scanf("%d%d", &s,&e );
nMax = MY_MAX;
nMin = MY_MIN;
Query( Tree, s, e );
printf("%d\n", nMax - nMin) ;
}
return 0;
}
posted on 2010-07-29 07:14
Vontroy 閱讀(268)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
線段樹|樹狀數(shù)組 、
POJ