題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1754 兩道題過(guò)后，我發(fā)覺(jué)線段樹(shù)單點(diǎn)更新裸寫法我已經(jīng)能寫個(gè)差不多了，繼續(xù)膜拜notonlysuccess大神 再做，再做，直到形成了我自己的模版深深刻在我腦子里為止！！
  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 const int maxn = 200000;
9 int MAX[maxn << 2];
10 void PushUp(int rt)
11 {
12 MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]);
13 }
14 void build(int l, int r, int rt)
15 {
16 if (l == r)
17 {
18 scanf("%d", &MAX[rt]);
19 return;
20 }
21 int m = (l + r) >> 1;
22 build(l, m, rt << 1);
23 build(m + 1, r, rt << 1 | 1);
24 PushUp(rt);
25 }
26 void update(int p, int t, int l, int r, int rt)
27 {
28 if (l == r)
29 {
30 MAX[rt] = t;
31 return;
32 }
33 int m = (l + r) >> 1;
34 if (p <= m) update(p, t, l, m, rt << 1);
35 else update(p, t, m + 1, r, rt << 1 | 1);
36 PushUp(rt);
37 }
38 int query(int ll, int rr, int l, int r, int rt)
39 {
40 if (ll <= l && rr >= r) return MAX[rt];
41 int m = (l + r) >> 1;
42 int ret = 0;
43 if (ll <= m) ret = max(ret, query(ll, rr, l, m, rt << 1));
44 if (rr > m) ret = max(ret, query(ll, rr, m + 1, r, rt << 1 | 1));
45 return ret;
46 }
47 int main()
48 {
49 int n, m;
50 while (scanf("%d%d", &n, &m) != EOF)
51 {
52 char c;
53 int x, y;
54 build(1, n, 1);
55 while(m--)
56 {
57 scanf("\n%c %d%d", &c, &x, &y);
58 if (c == 'U') update(x, y, 1, n, 1);
59 if (c == 'Q')
60 {
61 int ans = query(x, y, 1, n, 1);
62 printf("%d\n", ans);
63 }
64 }
65 }
66 return 0;
67
|