AHU-351 求最值之差 (RMQ问题+线段树&&ST算法)

Description

给出N个数，求第a个数到第b个数之间最大的数减去最小的数的结果

Input

N（N小于100,000），M（M小于100,000）
接下来有N个数
接下来M组范围,所有数均在[0,2³¹-1]内
每个范围有2个整数a,b(1<=a<=b<=N)

Output

每行输出一个结果

Sample Input

Sample Output

9
3
0

思路：
RMQ问题模板题，一开始用线段树写了一发，大材小用效率还不高，妥妥的ST算法。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define M(a, b) memset(a, b, sizeof(a))
 4 const int maxn = 1e5 + 10;
 5 int maxd[maxn][50], mind[maxn][50], n, _max, _min;
 6 
 7 void RMQ_init() {
 8     for (int j = 1; (1<<j) <= n; ++j)
 9         for (int i = 1; i + (1<<j) - 1 <= n; ++i) {
10             maxd[i][j] = max(maxd[i][j-1], maxd[i + (1<<(j-1))][j-1]);
11             mind[i][j] = min(mind[i][j-1], mind[i + (1<<(j-1))][j-1]);
12         }
13 }
14 
15 void RMQ(int L, int R) {
16     int k = 0;
17     while((1<<(k+1)) <= R-L+1) ++k;
18     _max = max(maxd[L][k], maxd[R-(1<<k)+1][k]);
19     _min = min(mind[L][k], mind[R-(1<<k)+1][k]);
20 }
21 
22 int main() {
23     int q, v, qL, qR;
24     while(~scanf("%d%d", &n, &q)) {
25         for (int i = 1; i <= n; ++i) {
26             scanf("%d", &v);
27             maxd[i][0] = mind[i][0] = v;
28         }
29         RMQ_init();
30         while(q--) {
31             scanf("%d%d", &qL, &qR);
32             RMQ(qL, qR);
33             printf("%d
", _max-_min);
34         }
35     }
36 
37     return 0;
38 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define M(a, b) memset(a, b, sizeof(a))
 4 #define INF 0x3f3f3f3f
 5 #define lson o<<1
 6 #define rson o<<1|1
 7 const int maxn = 1e5 + 10;
 8 int maxv[maxn<<2], minv[maxn<<2], _max, _min, v, qL, qR;
 9 
10 void build(int o, int L, int R) {
11     if (L == R) {
12         scanf("%d", &v);
13         maxv[o] = minv[o] = v;
14     }
15     else {
16         int M = (L + R) >> 1;
17         build(lson, L, M);
18         build(rson, M+1, R);
19         maxv[o] = max(maxv[lson], maxv[rson]);
20         minv[o] = min(minv[lson], minv[rson]);
21     }
22 }
23 
24 void query(int o, int L, int R) {
25     if (qL <= L && R <= qR) {
26         _max = max(_max, maxv[o]);
27         _min = min(_min, minv[o]);
28     }
29     else {
30         int M = (L + R) >> 1;
31         if (qL <= M) query(lson, L, M);
32         if (M < qR) query(rson, M+1, R);
33     }
34 }
35 
36 int main() {
37     int n, q;
38     while(~scanf("%d%d", &n, &q)) {
39         build(1, 1, n);
40         while(q--) {
41             scanf("%d%d", &qL, &qR);
42             _max = -1, _min = INF;
43             query(1, 1, n);
44             printf("%d
", _max-_min);
45         }
46     }
47 
48     return 0;
49 }