hdu 1754 线段树（单点替换区间最值）

Sample Input
5 6
1 2 3 4 5
Q 1 5 //1-5结点的最大值
U 3 6 //将点3的数值换成6
Q 3 4
Q 4 5
U 2 9
Q 1 5

Sample Output
5
6
5
9

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # include <queue>
 7 # define LL long long
 8 using namespace std ;
 9 
10 const int maxn = 200010;
11 
12 int MAX[maxn<<2] ; //结点开4倍
13 
14 void PushUP(int rt) //更新到父节点
15 {
16     MAX[rt] = max(MAX[rt * 2] , MAX[rt * 2 + 1] ); //rt 为当前结点
17 }
18 
19 void build(int l , int r , int rt) //构建线段树
20 {
21     if (l == r)
22     {
23         scanf("%d" , &MAX[rt]) ;
24         return ;
25     }
26     int m = (l + r) / 2 ;
27     build(l , m , rt * 2) ;
28     build(m + 1 , r , rt * 2 +1) ;
29     PushUP(rt) ;
30 }
31 
32 void updata(int p , int add , int l , int r , int rt)  //单点替换
33 {
34     if (l == r)
35     {
36         MAX[rt] = add ;
37         return ;
38     }
39     int m = (l + r) / 2 ;
40     if (p <= m)
41        updata(p , add , l , m , rt * 2) ;
42     else
43        updata(p , add , m + 1 , r , rt * 2 + 1) ;
44     PushUP(rt) ;
45 }
46 
47 int query(int L , int R , int l , int r , int rt)  //区间求最大值
48 {
49     if (L <= l && r <= R)
50         return MAX[rt] ;
51     int m = (l + r) / 2 ;
52     int ret = 0 ;
53     if (L <= m)
54        ret = max(ret , query(L , R , l , m , rt * 2) ) ;
55     if (R > m)
56        ret = max(ret , query(L , R , m + 1 , r , rt * 2 + 1) );
57     return ret ;
58 }
59 
60 int main ()
61 {
62     //freopen("in.txt","r",stdin) ;
63     int n , m ;
64     while(scanf("%d %d" , &n , &m) != EOF)
65     {
66         build(1 , n , 1) ;
67         char op[10] ;
68         while(m--)
69         {
70             scanf("%s" , op) ;
71             if (op[0] == 'E') //结束
72                break ;
73             int a , b ;
74             scanf("%d %d" , &a , &b) ;
75             if (op[0] == 'Q') //求a,b区间的和最大值
76                printf("%d
", query(a , b , 1 , n , 1))  ;
77             else if (op[0] == 'U')  //将第a个地方的值改为b
78                updata(a , b , 1 , n , 1) ;
79         }
80     }
81 
82     return 0 ;
83 }

View Code

hdu 1754 线段树（单点替换 区间最值）

hdu 1754 线段树（单点替换区间最值）