POJ

题目：poj.org/problem?id=3264

题意：求一段区间内最大值与最小值的差。

看到区间最值首先想到RMQ--ST算法。但本题出现在了kuangbin专题的线段树里。

用线段树也无思维难点，但有两个坑：

1. 查询函数中，区间不包含时的返回值。

2.用cin,cout会TLE。用c的输入方式。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<string>
 5 #include<vector>
 6 #include<list>
 7 #include<cmath>
 8 #include<set>
 9 #include<utility>
10 #include<algorithm>
11 using namespace std;
12 
13 
14 #define maxn 50010
15 int N, Q;
16 int cow[maxn];
17 struct node
18 {
19     int minn, maxx;
20 }tree[maxn*4];
21 
22 void build_tree(int l,int r,int i)
23 {
24     if (l == r)
25     {
26         tree[i].maxx = cow[l];
27         tree[i].minn = cow[l];
28         return;
29     }
30     int mid = (l + r) / 2;
31     build_tree(l, mid, i + i);
32     build_tree(mid + 1, r, i + i + 1);
33     tree[i].maxx = max(tree[i + i].maxx, tree[i + i + 1].maxx);
34     tree[i].minn = min(tree[i + i].minn, tree[i + i + 1].minn);
35 }
36 int querymax(int tl, int tr, int l, int r, int i)
37 {
38     if (tl > r || tr < l)return 0;
39     if (tl <= l&&r <= tr)
40     {
41         return tree[i].maxx;
42     }
43     int mid = (l + r) / 2;
44     return max(querymax(tl, tr, l, mid, i + i) , querymax(tl, tr, mid + 1, r, i + i + 1));
45 }
46 int querymin(int tl, int tr, int l, int r, int i)
47 {
48     if (tl > r || tr < l)
49         return INT_MAX;//这里return返回的值要注意
50     if (tl <= l&&r <= tr)
51     {
52         return tree[i].minn;
53     }
54     int mid = (l + r) / 2;
55     return min(querymin(tl, tr, l, mid, i + i), querymin(tl, tr, mid + 1, r, i + i + 1));
56 }
57 int main()
58 {
59 
60     scanf("%d%d", &N, &Q);
61     for (int i = 1; i <= N; i++)
62         scanf("%d", &cow[i]);
63     build_tree(1, N, 1); 
64     int a, b;
65     for (int i = 1; i <= Q; i++)
66     {
67         scanf("%d%d", &a, &b);
68         if (a == b)
69         {
70             cout << "0" << endl; continue;
71         }
72         int qjmax = querymax(a, b, 1, N, 1);
73         int qjmin = querymin(a, b, 1, N, 1);
74         printf("%d
", qjmax - qjmin);
75     }
76     return 0;
77 }

View Code