poj3264 Balanced Lineup

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int MAXN = 65536;
 7 const int INF = 0x3f3f3f3f;
 8 
 9 struct node
10 {
11     int maxn, minn;
12 };
13 
14 node data[2 * MAXN - 1];
15 int n, q, x, y, tmp;
16 
17 void init(int n_)
18 {
19     n = 1;
20     while (n < n_)
21     {
22         n *= 2;
23     }
24     for (int i = 0; i < 2 * n - 1; i++)
25     {
26         data[i].maxn = -INF;
27         data[i].minn = INF;
28     }
29 }
30 
31 void update(int k, int a)
32 {
33     k += n - 1;
34     data[k].minn = data[k].maxn = a;
35     while (k)
36     {
37         k = (k - 1) / 2;
38         data[k].minn = min(data[2 * k + 1].minn, data[2 * k + 2].minn);
39         data[k].maxn = max(data[2 * k + 1].maxn, data[2 * k + 2].maxn);
40     }
41 }
42 
43 int query(int a, int b, int k, int l, int r, int type) 
44 {
45     if (r <= a || l >= b)
46     {
47         if (type)
48             return INF;
49         else
50             return -INF;
51     }
52     if (l >= a && r <= b)
53     {
54         if (type)
55             return data[k].minn;
56         else
57             return data[k].maxn;
58     }
59     int x = query(a, b, 2 * k + 1, l, (l + r) / 2, type);
60     int y = query(a, b, 2 * k + 2, (l + r) / 2, r, type);
61     if (type)
62         return min(x, y);
63     return max(x, y);
64 }
65 
66 int main()
67 {
68     scanf("%d %d", &n, &q);
69     int n_ = n;
70     init(n);
71     for (int i = 0; i < n_; i++)
72     {
73         scanf("%d", &tmp);
74         update(i, tmp);
75     }
76     for (int i = 0; i < q; i++)
77     {
78         scanf("%d %d", &x, &y);
79         int s = query(x - 1, y, 0, 0, n, 1);
80         int t = query(x - 1, y, 0, 0, n, 0);
81         printf("%d
", t - s);
82     }
83     return 0;
84 }

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 const int MAXN = 50005;
 6 const int INF = 0x3f3f3f3f;
 7 int a[MAXN], minn[MAXN * 4], maxn[MAXN * 4], n, m;
 8 
 9 void build(int num, int l, int r)
10 {
11     if (l == r) { maxn[num] = minn[num] = a[l]; return; }
12     int m = l + r >> 1;
13     build(num * 2, l, m);
14     build(num * 2 + 1, m + 1, r);
15     maxn[num] = max(maxn[num * 2], maxn[num * 2 + 1]);
16     minn[num] = min(minn[num * 2], minn[num * 2 + 1]);
17 }
18 
19 int query(int num, int l, int r, int x, int y, int type)
20 {
21     if (x <= l && y >= r) return type ? maxn[num] : minn[num];
22     int m = l + r >> 1;
23     int ans = type ? -INF : INF;
24     if (x <= m) 
25     { 
26         int tmp = query(num * 2, l, m, x, y, type); 
27         ans = type ? max(ans, tmp) : min(ans, tmp);
28     }
29     if (y >= m + 1)
30     {    
31         int tmp = query(num * 2 + 1, m + 1, r, x, y, type);
32         ans = type ? max(ans, tmp) : min(ans, tmp);
33     }
34     return ans;
35 }
36 
37 int main()
38 {
39     int l, r;
40     scanf("%d %d", &n, &m);
41     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
42     build(1, 1, n);
43     for (int i = 0; i < m; i++) 
44     {
45         scanf("%d %d", &l, &r);
46         printf("%d
", query(1, 1, n, l, r, 1) - query(1, 1, n, l, r, 0));
47     }
48     return 0;
49 }