POJ 3264 Balanced Lineup
Description
Input
Output
Sample Input
Sample Output
解题思路:
AC代码:

题目原网址:http://poj.org/problem?id=3264

题目中文翻译:

对于每日的挤奶，农夫约翰的奶牛（1≤N≤50,000）始终按照相同的顺序排列。有一天，农夫约翰决定与一些奶牛组织一场极限飞盘游戏。为了简单起见，他会从挤奶阵容中挑选连续的奶牛进行比赛。但是，为了让所有的母牛玩得开心，它们的高度不应该太高。

农民约翰列出了Q（1≤Q≤200 000）个牛群及其高度（1≤高度≤1,000,000）。对于每个小组，他都希望得到你的帮助，以确定小组中最矮的和最高的牛之间的身高差异。

Input

第1行：两个空格分隔的整数N和Q.

第2..N + 1行：第i + 1行包含一个整数，即牛i的高度

第N + 2..N + Q + 1行：两个整数A和B（1≤A≤B≤N），表示母牛从A到B的范围。

Output

第1..Q行：每行包含一个整数，它是对查询的响应，指示范围中最高和最低牛之间的高度差。

Sample Input

6 3

1 5

4 6

2 2

Sample Output

解题思路:

一道很裸的线段树求区间最大值和最小值,详细注释看代码.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 
 6 bool bj;
 7 int n,q,a[2000001];
 8 struct kkk{
 9     int l,r;//l,r分别表示当前节点表示区间的最左点位置和最右点位置 
10     long long da,xiao;//da表示区间最大值,xiao表示区间最小值 
11 }t[2000001];
12 
13 void build(int ll,int rr,int h) {
14     t[h].l = ll;t[h].r = rr;
15     if(ll == rr) {
16         t[h].da = a[ll];
17         t[h].xiao = a[ll];
18         return ;
19     }             
20     int mid = (ll + rr) >> 1;
21     build(ll,mid,h * 2);
22     build(mid + 1,rr,h * 2 + 1);
23     t[h].da = max(t[h*2].da , t[h*2+1].da); 
24     t[h].xiao = min(t[h*2].xiao , t[h*2+1].xiao);
25 }
26 
27 int findmax(int ll,int rr,int h) {
28     bj = 0;
29     if(ll == t[h].l && rr == t[h].r) return t[h].da;//一定是所求区间和包含区间完全一致 
30     int mid = (t[h].l + t[h].r) >> 1;
31     int _max = -100;
32     if(rr <= mid) _max = max(_max,findmax(ll,rr,h*2)),bj = 1;//所求区间在包含区间左半边,只递归左儿子 
33     else if(ll > mid) _max = max(_max,findmax(ll,rr,h * 2 + 1)),bj = 1;//所求区间在包含区间右半边,只递归右儿子 
34     else _max = max(_max,max(findmax(ll,mid,h*2),findmax(mid+1,rr,h*2+1)));//所求区间在包含区间左右半边都有,则两个儿子都递归 
35     return _max;
36 }
37 
38 int findmin(int ll,int rr,int h) {
39     bj = 0;
40     if(ll == t[h].l && rr == t[h].r) return t[h].xiao;//一定是所求区间和包含区间完全一致 
41     int mid = (t[h].l + t[h].r) >> 1;
42     int _min = 10000000;
43     if(rr <= mid) _min = min(_min,findmin(ll,rr,h*2)),bj = 1;//所求区间在包含区间左半边,只递归左儿子 
44     else if(ll > mid) _min = min(_min,findmin(ll,rr,h * 2 + 1)),bj = 1;//所求区间在包含区间右半边,只递归右儿子 
45     else _min = min (_min ,min(findmin(ll,mid,h*2),findmin(mid+1,rr,h*2+1)));//所求区间在包含区间左右半边都有,则两个儿子都递归 
46     return _min;
47 }
48 
49 int main() {
50     scanf("%d%d",&n,&q);
51     for(int i = 1;i <= n; i++) scanf("%d",&a[i]);
52     build(1,n,1); //构建线段树 
53     for(int i = 1;i <= q; i++) {
54         int L,R;
55         scanf("%d%d",&L,&R);
56         if(L == R) printf("0
");//求长度为1的区间直接输出0,节省时间 
57         else
58             printf("%d
",findmax(L,R,1) - findmin(L,R,1));//这两个函数与线段树加法不太一样 
59     }
60     
61     return 0;
62 }

POJ 3264 Balanced Lineup Description Input Output Sample Input Sample Output 解题思路: AC代码: