题目链接：http://poj.org/problem?id=3264 裸裸的线段树，就是一个结点存储两个值，一个是区间内最大值，一个是区间内最小值，最后做个差了事儿～～这两天被很多题虐爆了，今天放松一下心情……
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define lson l, m, rt << 1
9 #define rson m + 1, r, rt << 1 | 1
10 const int maxn = 50010;
11 int MAX[maxn << 2], MIN[maxn << 2];
12 void PushUp(int rt)
13 {
14 MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]);
15 MIN[rt] = min(MIN[rt << 1], MIN[rt << 1 | 1]);
16 }
17 void build(int l, int r, int rt)
18 {
19 if (l == r)
20 {
21 scanf("%d", &MAX[rt]);
22 MIN[rt] = MAX[rt];
23 return;
24 }
25 int m = (l + r) >> 1;
26 build(lson);
27 build(rson);
28 PushUp(rt);
29 }
30 int queryzg(int ll, int rr, int l, int r, int rt)
31 {
32 if (ll <= l && rr >= r) return MAX[rt];
33 int m = (l + r) >> 1;
34 int ret = 0;
35 if (ll <= m) ret = max(ret, queryzg(ll, rr, lson));
36 if (rr > m) ret = max(ret, queryzg(ll,rr, rson));
37 return ret;
38 }
39 int queryza(int ll, int rr, int l, int r, int rt)
40 {
41 if (ll <= l && rr >= r) return MIN[rt];
42 int m = (l + r) >> 1;
43 int ret = 210000000;
44 if (ll <= m) ret = min(ret, queryza(ll, rr, lson));
45 if (rr > m) ret = min(ret, queryza(ll, rr, rson));
46 return ret;
47 }
48 int main()
49 {
50 int n, q;
51 while (scanf("%d%d", &n, &q) != EOF)
52 {
53 build(1, n, 1);
54 while (q--)
55 {
56 int x, y;
57 scanf("%d%d", &x, &y);
58 int da = queryzg(x, y, 1, n, 1);
59 int xi = queryza(x, y, 1, n, 1);
60 int ans = da - xi;
61 printf("%d\n", ans);
62 }
63 }
64 return 0;
65 }
66
|