数据结构专题训练

 1 /*************************************************************************
 2     > File Name: hdu1754.cpp
 3     > Author: syhjh
 4     > Created Time: 2014年03月20日 星期四 21时52分56秒
 5  ************************************************************************/
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <algorithm>
10 using namespace std;
11 
12 #define lson rt << 1
13 #define rson rt << 1 | 1
14 const int MAXN = (200000 + 200);
15 template < class T > inline T getMax(const T &a, const T &b)
16 {
17     return a > b ? a : b;
18 }
19 
20 int sum[MAXN << 2];
21 int N, M;
22 
23 void PushUp(int rt)
24 {
25     sum[rt] = getMax(sum[lson], sum[rson]);
26 }
27 
28 void Build(int L, int R, int rt)
29 {
30     if (L == R) {
31         scanf("%d", &sum[rt]);
32         return;
33     }
34     int M = (L + R) >> 1;
35     Build(L, M, lson);
36     Build(M + 1, R, rson);
37     PushUp(rt);
38 }
39 
40 void Update(int L, int R, int rt, int p, int x)
41 {
42     if (L == R) {
43         sum[rt] = x;
44         return;
45     }
46     int M = (L + R) >> 1;
47     if (p <= M) {
48         Update(L, M, lson, p, x);
49     } else 
50         Update(M + 1, R, rson, p, x);
51     PushUp(rt);
52 }
53 
54 int Query(int L, int R, int rt, int l, int r)
55 {
56     if (l <= L && R <= r) {
57         return sum[rt];
58     }
59     int M = (L + R) >> 1;
60     int res = 0;
61     if (l <= M) res = getMax(res, Query(L, M, lson, l, r));
62     if (r > M) res = getMax(res, Query(M + 1, R, rson, l, r));
63     return res;
64 }
65 
66 int main()
67 {
68     while (cin >> N >> M) {
69         Build(1, N, 1);
70         while (M--) {
71             char str[11];
72             int x, y;
73             scanf("%s", str);
74             if (str[0] == ‘U‘) {
75                 scanf("%d %d", &x, &y);
76                 Update(1, N, 1, x, y);
77             } else if (str[0] == ‘Q‘) {
78                 scanf("%d %d", &x, &y);
79                 int ans =  Query(1, N, 1, x, y);
80                 printf("%d\n", ans);
81             }
82         }
83     }
84     return 0;
85 }