洛谷P1531我讨厌它——线段树实现

 1 #include 
 2 #include 
 3 #include 
 4 using namespace std;
 5 
 6 const int MAXN = 200011;
 7 struct Node {
 8     int l, r, mx;
 9 } tree[4 * MAXN];
10 int a[MAXN], n, Q, ans, x, y;
11 char op[2];
12 
13 inline int read() {
14     char ch = getchar();
15     int x = 0, f = 1;
16     while (ch <'0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
17     while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
18     return x * f;
19 }
20 
21 inline void pushup(int root) {
22     tree[root].mx = max(tree[root * 2].mx, tree[root * 2 + 1].mx);
23 }
24 
25 inline void build(int l, int r, int root) {
26     tree[root].l = l; tree[root].r = r;
27     if (l == r) {
28         tree[root].mx = a[l];
29         return;
30     }
31     int mid = (l + r) / 2;
32     build(l, mid, root * 2);
33     build(mid + 1, r, root * 2 + 1);
34     pushup(root);
35 }
36 
37 inline void update(int pos, int val, int root) {
38     if (tree[root].l == tree[root].r) {
39         if (val > tree[root].mx) tree[root].mx = val;
40         return;
41     }
42     int mid = (tree[root].l + tree[root].r) / 2;
43     if (pos <= mid) update(pos, val, root * 2);
44     else update(pos, val, root * 2 + 1);
45     pushup(root);
46 }
47 
48 inline int query(int l, int r, int root) {
49     if (tree[root].l == l && tree[root].r == r) return tree[root].mx;
50     int mid = (tree[root].l + tree[root].r) / 2;
51     if (l > mid) return query(l, r, root * 2 + 1);
52     if (r <= mid) return query(l, r, root * 2);
53     int res = max(query(l, mid, root * 2), query(mid + 1, r, root * 2 + 1));
54     return res;
55 }
56 
57 int main() {
58     n = read(); Q = read();
59     for (int i = 1; i <= n; i++) a[i] = read();
60     build(1, n, 1);
61     
62     for (int i = 1; i <= Q; i++) {
63         scanf("%s", op);
64         x = read(); y = read();
65         if (op[0] == 'U') update(x, y, 1);
66         else {
67             ans = query(x, y, 1);
68             printf("%d\n", ans);
69         }
70     }
71     return 0;
72 }