hdu1754 I Hate It

线段树功能:update:单点替换 query:区间最值

这是一道最基本的线段树的题。

只需要建树，然后对树的节点更新。

然后是询问区间的和。

View Code

 1 #include<iostream>
 2 #include<string>
 3 #include<queue>
 4 #include<map>
 5 #include<stack>
 6 #include<cmath>
 7 #include<functional>
 8 #include<algorithm>
 9 using namespace std;
10 #define lson l , m , rt << 1
11 #define rson m + 1 , r , rt << 1 | 1
12 const int maxn = 220000;
13 int sum[maxn<<2];
14 int n;
15 
16 int operate(int a,int b){
17     return max(a,b);
18 }
19 
20 void PushUp(int rt){
21     sum[rt]=operate(sum[rt<<1],sum[rt<<1|1]);
22 }
23 
24 void bulid(int l=1,int r=n,int rt=1){
25     if(l==r){
26         scanf("%d",&sum[rt]);return ;
27     }
28     int m=(l+r)>>1;
29     bulid(lson);
30     bulid(rson);
31     PushUp(rt);
32 }
33 
34 void update(int p,int add,int l=1,int r=n,int rt=1){
35     if(l==r){
36         sum[rt]=add;return ;
37     }
38     int m=(l+r)>>1;
39     if(p<=m)update(p,add,lson);
40     else update(p,add,rson);
41     PushUp(rt);
42 }
43 
44 int query(int L,int R,int l=1,int r=n,int rt=1){
45     if(L<=l && r<=R){
46         return sum[rt];
47     }
48     int m=(l+r)>>1;
49     int ans=0;
50     if(L<=m)ans=operate(ans,query(L,R,lson));
51     if(R> m)ans=operate(ans,query(L,R,rson));
52     return ans;
53 }
54 
55 
56 int main(){
57     
58     int m;
59     while(~scanf("%d%d",&n,&m)){
60         bulid();
61         char op[2];        
62         while(m--){
63             int a,b;
64             scanf("%s%d%d",op,&a,&b);
65             if(op[0]=='Q')printf("%d\n",query(a,b));
66             else update(a,b);
67         }
68     }
69 
70     return 0;
71 }