題目鏈接：http://www.lightoj.com/volume_showproblem.php?problem=1082 真心不解釋，如果加一個U操作簡直可以跟前幾天發(fā)的某一道題配對兒了。。
  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 = 100010;
11 int MIN[maxn << 2];
12 void PushUp(int rt)
13 {
14 MIN[rt] = min(MIN[rt << 1], MIN[rt << 1 | 1]);
15 }
16 void build(int l, int r, int rt)
17 {
18 if (l == r)
19 {
20 scanf("%d", &MIN[rt]);
21 return;
22 }
23 int m = (l + r) >> 1;
24 build(lson);
25 build(rson);
26 PushUp(rt);
27 }
28 int query(int ll, int rr, int l, int r, int rt)
29 {
30 if (ll <= l && rr >= r) return MIN[rt];
31 int m = (l + r) >> 1;
32 int ret = maxn;
33 if (ll <= m) ret = min(ret, query(ll, rr, lson));
34 if (rr > m) ret = min(ret, query(ll, rr, rson));
35 return ret;
36 }
37 int main()
38 {
39 int t;
40 scanf("%d", &t);
41 for (int i = 1; i <= t; i++)
42 {
43 printf("Case %d:\n", i);
44 int n, m; scanf("%d%d", &n, &m);
45 build(1, n, 1);
46 while (m--)
47 {
48 int x, y;
49 scanf("%d%d", &x, &y);
50 int ans = query(x, y, 1, n, 1);
51 printf("%d\n", ans);
52 }
53 }
54 return 0;
55
|