（线段树）Balanced Lineup --POJ --3264

链接：

对于POJ老是爆，我也是醉了，链接等等再发吧！

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82832#problem/G

只是简单的建树，每个节点上记录它的最大值和最小值，最后查询一下，就ok了

代码：

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<iostream>
 7 const int N = 50005;
 8 using namespace std;
 9 
10 #define Lson r<<1
11 #define Rson r<<1|1
12 #define mid  a[r].Mid()
13 
14 struct node
15 {
16     int L, R;
17     int Max, Min;
18     int Mid()
19     {
20         return (L+R)>>1;
21     }
22     int len()
23     {
24         return (R-L+1);
25     };
26 } a[N<<2];
27 
28 void BuildTree(int r, int L, int R)
29 {
30     a[r].L=L, a[r].R=R;
31 
32     if(L==R)
33     {
34         scanf("%d", &a[r].Min);
35         a[r].Max = a[r].Min;
36         return ;
37     }
38 
39     BuildTree(Lson, L, mid);
40     BuildTree(Rson, mid+1, R);
41 
42     a[r].Min = min(a[Lson].Min, a[Rson].Min);
43     a[r].Max = max(a[Lson].Max, a[Rson].Max);
44 }
45 
46 int QueryMax(int r, int L, int R)
47 {
48     if(a[r].L==L && a[r].R==R)
49         return a[r].Max;
50 
51     if(R<=mid)
52         return  QueryMax(Lson, L, R);
53     else if(L>mid)
54         return  QueryMax(Rson, L, R);
55     else
56     {
57         return max(QueryMax(Lson, L, mid), QueryMax(Rson, mid+1, R));
58     }
59 }
60 
61 int QueryMin(int r, int L, int R)
62 {
63     if(a[r].L==L && a[r].R==R)
64         return a[r].Min;
65 
66     if(R<=mid)
67         return  QueryMin(Lson, L, R);
68     else if(L>mid)
69         return  QueryMin(Rson, L, R);
70     else
71     {
72         return min(QueryMin(Lson, L, mid), QueryMin(Rson, mid+1, R));
73     }
74 }
75 
76 
77 
78 int main()
79 {
80     int n, m;
81     while(scanf("%d%d", &n, &m)!=EOF)
82     {
83 
84     BuildTree(1, 1, n);
85 
86     int L, R;
87 
88     while(m--)
89     {
90         scanf("%d%d", &L, &R);
91         printf("%d
", QueryMax(1, L, R)-QueryMin(1, L, R));
92     }
93     }
94 
95     return 0;
96 }

勿忘初心