题目链接:http://poj.org/problem?id=3264

作者:kuangbin(转载请注明出处,谢谢!!)

更多详细文章,请访问博客:www.cnblogs.com/kuangbin

 

ACM POJ 3264 Balanced Lineup

这到题目是线段树的练习题目。

很简单,练练手!!

AC程序:

/*
POJ 3264 Balanced Lineup
题目意思:给定Q(1<=Q<=200000)个数A1,A2,```,AQ,
多次求任一区间Ai-Aj中最大数和最小数的差
*/
#include
<stdio.h>
#include
<algorithm>
#include
<iostream>
using namespace std;
#define MAXN 200005
#define INF 10000000
int nMax,nMin;//记录最大最小值
struct Node
{
int l,r;//区间的左右端点
int nMin,nMax;//区间的最小值和最大值
}segTree[MAXN*3];
int a[MAXN];
void Build(int i,int l,int r)//在结点i上建立区间为(l,r)
{
segTree[i].l
=l;
segTree[i].r
=r;
if(l==r)//叶子结点
{
segTree[i].nMin
=segTree[i].nMax=a[l];
return;
}
int mid=(l+r)>>1;
Build(i
<<1,l,mid);
Build(i
<<1|1,mid+1,r);
segTree[i].nMin
=min(segTree[i<<1].nMin,segTree[i<<1|1].nMin);
segTree[i].nMax
=max(segTree[i<<1].nMax,segTree[i<<1|1].nMax);
}
void Query(int i,int l,int r)//查询结点i上l-r的最大值和最小值
{
if(segTree[i].nMax<=nMax&&segTree[i].nMin>=nMin) return;
if(segTree[i].l==l&&segTree[i].r==r)
{
nMax
=max(segTree[i].nMax,nMax);
nMin
=min(segTree[i].nMin,nMin);
return;
}
int mid=(segTree[i].l+segTree[i].r)>>1;
if(r<=mid) Query(i<<1,l,r);
else if(l>mid) Query(i<<1|1,l,r);
else
{
Query(i
<<1,l,mid);
Query(i
<<1|1,mid+1,r);
}
}
int main()
{
int n,q;
int l,r;
int i;
while(scanf("%d%d",&n,&q)!=EOF)
{
for(i=1;i<=n;i++)
scanf(
"%d",&a[i]);
Build(
1,1,n);
for(i=1;i<=q;i++)
{
scanf(
"%d%d",&l,&r);
nMax
=-INF;nMin=INF;
Query(
1,l,r);
printf(
"%d\n",nMax-nMin);
}
}
return 0;
}

另外附一参考程序:

#include <iostream>
#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];
//CNode Tree[20];
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)
{
if( pRoot->L == i && pRoot->R == i ) {
pRoot
->nMin = pRoot->nMax = v;
return;
}
pRoot
->nMin = _cpp_min(pRoot->nMin,v);
pRoot
->nMax = _cpp_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->nMin >= nMin && pRoot->nMax <= nMax )
return;
if( s == pRoot->L && e == pRoot->R) {
nMin
= _cpp_min(pRoot->nMin,nMin);
nMax
= _cpp_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\n",nMax - nMin);
}
return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2011/08/14/2137862.html