HDU 1754 I Hate It(线段树)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define Maxn 200001
 5 using namespace std;
 6 struct Node{
 7     int left;
 8     int right;
 9     int max;
10 };
11 Node Tree[Maxn * 20];//要开大些
12 int Num[Maxn];
13 int Builder(int root, int left, int right)
14 {
15     Tree[root].left = left;
16     Tree[root].right = right;
17     if(left == right){
18         return Tree[root].max = Num[left];
19     }
20     int mid = (left + right) / 2;
21     int L = Builder(2 * root, left, mid);
22     int R = Builder(2 * root + 1, mid + 1, right);
23     return Tree[root].max = max(L, R);
24 }
25 int Update(int root, int pos, int val)
26 {
27     //pos 不在root管理的区间内
28     if(pos < Tree[root].left || pos > Tree[root].right){
29         return Tree[root].max;
30     }
31     //找到pos点
32     if(Tree[root].left == pos && Tree[root].right == pos){
33         return Tree[root].max = val;
34     }
35     int L = Update(2 * root, pos, val);
36     int R = Update(2 * root + 1, pos, val);
37     return Tree[root].max = max(L, R);
38 }
39 int Find(int root, int left, int right)
40 {
41     //不包含
42     if(Tree[root].left > right || Tree[root].right < left){
43         return 0;
44     }
45     //包含
46     if(left <= Tree[root].left && Tree[root].right <= right){
47         return Tree[root].max;
48     }
49     //部分相交
50     int L = Find(2 * root, left, right);
51     int R = Find(2 * root + 1, left, right);
52     return max(L, R);
53 }
54 
55 int main()
56 {
57     int i, j, n, m, p, v;
58     char c;
59     while(~scanf("%d%d", &n, &m))
60     {
61         for(i = 1; i <= n; i++){
62             scanf("%d", &Num[i]);
63         }
64         Builder(1, 1, n);
65         for(i = 1; i <= m; i++){
66             getchar();
67             scanf("%c %d%d", &c, &p, &v);
68             if(c == ‘U‘){
69                 Update(1, p, v);
70             }
71             else{
72                 printf("%d\n", Find(1, p, v));
73             }
74         }
75     }
76     return 0;
77 }