本文主要是介绍POJ 3264 Balanced Lineup 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A - Balanced Lineup
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 2Sample Output
6
3
0
题意就是找出区间内最大值最小值之差，刚学线段树，就拿这道题练了练手，代码有些繁琐。
看视频学的线段树，https://www.bilibili.com/video/av9350697?t=814
#include<stdio.h>
#include<iostream>
using namespace std;
struct node{
int left,right,value,small;//value最大 small最小
bool ex;//一开始做的时候最小值好多出现0 为了避免，当二叉树中存在该节点时才对其进行比较
};
int max(int x,int y)
{return x>y?x:y;
}
int min(int x,int y)
{if(x==0)return y;else if(y==0)return x;elsereturn x<y?x:y;}
node tree[200005];//50000 到二叉树里得开4*50000，完全二叉树2*50000
int height [50005];
void build_tree(int i,int le,int ri)//建树 初始化
{tree[i].left=le;tree[i].right=ri;tree[i].value=0;tree[i].small=0;tree[i].ex=true;if(le==ri){tree[i].value=height[le];tree[i].small=height[le];return ;}build_tree(i<<1,le,(le+ri)>>1);build_tree((i<<1)+1,((le+ri)>>1)+1,ri);
}
int MAX;
int MIN;
void query(int i,int left,int right)//查找函数
{if(right==tree[i].right&&left==tree[i].left){MAX=max(tree[i].value,MAX);MIN=min(tree[i].small,MIN);return ;}i=i<<1;if(left<=tree[i].right){if(right<=tree[i].right)query(i,left,right);elsequery(i,left,tree[i].right);}i=i+1;if(right>=tree[i].left){if(left>=tree[i].left)query(i,left,right);elsequery(i,tree[i].left,right);}
}
int main()
{
int N,Q;
int i;
int j,k;
cin>>N>>Q;for(i=0;i<100005;i++)tree[i].ex=false;
for(i=1;i<=N;i++)
{scanf("%d",&height[i]);
}
build_tree(1,1,N);
for(i=4*N-1;i>=1;i=i-2)
{if(tree[i].ex==true&&tree[i-1].ex==true&&tree[i/2].ex==true&&(tree[i].small!=0||tree[i-1].small!=0)){tree[i/2].value=max( tree[i].value,tree[i-1].value);tree[i/2].small=min( tree[i].small,tree[i-1].small);}}//因为只有二叉树叶子value和small有值，所以更新对他们父节点赋值
int x,y;for(i=1;i<=Q;i++)
{MAX=0;MIN=10000005;
scanf("%d%d",&x,&y);
query(1,x,y);
printf("%d\n",-MIN+MAX);}return 0;
}
这篇关于POJ 3264 Balanced Lineup 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
