POJ 3264 Balanced Lineup(线段树求区间最大最小值)

  1 // #pragma comment(linker, "/STACK:102400000,102400000")
  2 #include <cstdio>
  3 #include <iostream>
  4 #include <cstring>
  5 #include <string>
  6 #include <cmath>
  7 #include <set>
  8 #include <list>
  9 #include <map>
 10 #include <iterator>
 11 #include <cstdlib>
 12 #include <vector>
 13 #include <queue>
 14 #include <stack>
 15 #include <algorithm>
 16 #include <functional>
 17 using namespace std;
 18 typedef long long LL;
 19 #define ROUND(x) round(x)
 20 #define FLOOR(x) floor(x)
 21 #define CEIL(x) ceil(x)
 22 const int maxn = 100010;
 23 const int maxm = 0;
 24 const int inf = 0x3f3f3f3f;
 25 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL;
 26 const double INF = 1e30;
 27 const double eps = 1e-6;
 28 int N, Q;
 29 int n;
 30 int seq[maxn];
 31 struct Node
 32 {
 33     int l, r;
 34     int ll, rr;
 35     int minx;
 36     int maxx;
 37     Node(int _l = -1, int _r = -1, int _ll = -1, int _rr = -1, int _minx = -1, int _maxx = -1): l(_l), r(_r), ll(_ll), rr(_rr), minx(_minx), maxx(_maxx) {}
 38 };
 39 Node node[maxn * 10];
 40 void init()
 41 {
 42     n = 0;
 43 }
 44 void input()
 45 {
 46     scanf("%d%d", &N, &Q);
 47     for (int i = 1; i <= N; i++)
 48     {
 49         scanf("%d", &seq[i]);
 50     }
 51 }
 52 void debug()
 53 {
 54     cout << node[6].minx << " " << node[6].maxx << endl;
 55     cout << node[8].minx << " " << node[8].maxx << endl;
 56 }
 57 int getmin(int l, int r, int fa)
 58 {
 59     if (l == node[fa].l && r == node[fa].r) return node[fa].minx;
 60     int m = (node[fa].l + node[fa].r) >> 1;
 61     int ret = inf;
 62     if (r <= m)
 63     {
 64         ret = min(ret, getmin(l, r, node[fa].ll));
 65     }
 66     else if (l > m)
 67     {
 68         ret = min(ret, getmin(l, r, node[fa].rr));
 69     }
 70     else
 71     {
 72         ret = min(ret, getmin(l, m, node[fa].ll));
 73         ret = min(ret, getmin(m + 1, r, node[fa].rr));
 74     }
 75     return ret;
 76 }
 77 int getmax(int l, int r, int fa)
 78 {
 79     if (l == node[fa].l && r == node[fa].r) return node[fa].maxx;
 80     int m = (node[fa].l + node[fa].r) >> 1;
 81     int ret = 0;
 82     if (r <= m)
 83     {
 84         ret = max(ret, getmax(l, r, node[fa].ll));
 85     }
 86     else if (l > m)
 87     {
 88         ret = max(ret, getmax(l, r, node[fa].rr));
 89     }
 90     else
 91     {
 92         ret = max(ret, getmax(l, m, node[fa].ll));
 93         ret = max(ret, getmax(m + 1, r, node[fa].rr));
 94     }
 95     return ret;
 96 }
 97 int build(int l, int r)
 98 {
 99     int now = n;
100     n++;
101     node[now] = Node(l, r, -1, -1,  -1, -1);
102     if (l == r)
103     {
104         node[now].minx = min(seq[l], seq[r]);
105         node[now].maxx = max(seq[l], seq[r]);
106         return now;
107     }
108     int m = (l + r) >> 1;
109     node[now].ll = build(l, m);
110     node[now].rr = build(m + 1, r);
111     node[now].minx = min(node[node[now].ll].minx, node[node[now].rr].minx);
112     node[now].maxx = max(node[node[now].ll].maxx, node[node[now].rr].maxx);
113     return now;
114 }
115 void solve()
116 {
117     build(1, N);
118     while (Q--)
119     {
120         int l, r;
121         scanf("%d%d", &l, &r);
122         printf("%d
", getmax(l, r, 0) - getmin(l, r, 0));
123     }
124 }
125 void output()
126 {
127     //
128 }
129 int main()
130 {
131     // std::ios_base::sync_with_stdio(false);
132     // #ifndef ONLINE_JUDGE
133     // freopen("in.cpp", "r", stdin);
134     // #endif
135 
136     init();
137     input();
138     solve();
139     output();
140     return 0;
141 }