本文主要是介绍Balanced Lineup POJ-3264（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
For the daily milking, Farmer John’s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.
Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.
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
Lines 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 response to a reply and indicates the difference in height between the tallest and shortest 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
题意：第一行两个数m和m，接下来n行为数组中的每个数值，接着m行查询数据，每行两个数代表一段区间，输出这个区间中最大数和最小数的差值。
思路： 构造线段树，求出任意区间的最大和最小值，输出差值。
这个代码用G++提交是wrong answer，用C++提交就过了，纳闷。
代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=5e4+10;
int ma[maxn<<2],mi[maxn<<2];
int n,m;
int a[maxn<<2];
void build(int l,int r,int p)
{if(l==r){ma[p]=a[l];mi[p]=a[l];return ;}int mid=(l+r)>>1;build(l,mid,p<<1);build(mid+1,r,p<<1|1); ma[p]=max(ma[p<<1],ma[p<<1|1]);mi[p]=min(mi[p<<1],mi[p<<1|1]);
}
int query1(int l,int r,int ll,int rr,int p)//找最大值
{if(l==ll&&r==rr)return ma[p];int mid=(l+r)>>1;if(rr<=mid)//如果当前区间的右节点小于所需查找区间的中点则查找左子树query1(l,mid,ll,rr,p<<1);else if(ll>mid)//如果当前区间的左节点小于所需查找区间的中点则查找右子树query1(mid+1,r,ll,rr,p<<1|1);else//如果当前区间与所需查找区间的左子树和右子树都有交集，则分别查找左子树和右子树return max(query1(l,mid,ll,mid,p<<1),query1(mid+1,r,mid+1,rr,p<<1|1));
}
int query2(int l,int r,int ll,int rr,int p)//找最小值
{if(l==ll&&r==rr)return mi[p];int mid=(l+r)>>1;if(rr<=mid)//如果当前区间的右节点小于所需查找区间的中点则查找左子树query2(l,mid,ll,rr,p<<1);else if(ll>mid)//如果当前区间的左节点小于所需查找区间的中点则查找右子树query2(mid+1,r,ll,rr,p<<1|1);else//如果当前区间与所需查找区间的左子树和右子树都有交集，则分别查找左子树和右子树return min(query2(l,mid,ll,mid,p<<1),query2(mid+1,r,mid+1,rr,p<<1|1));
}
int main()
{while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,n,1);//建立线段树while(m--){int t1,t2;scanf("%d%d",&t1,&t2);int ans=query1(1,n,t1,t2,1)-query2(1,n,t1,t2,1);printf("%d\n",ans);}}return 0;
}
这篇关于Balanced Lineup POJ-3264（线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
