HDU 1754 I Hate It（线段树单点更新求区间最值）

http://acm.hdu.edu.cn/showproblem.php?pid=1754

题意

中文题面不解释

思路

就是一个单点更新求区间最值的裸题，给新手入门线段树比较好，有什么问题留言吧。

 1 #define IO std::ios::sync_with_stdio(0);
 2 #include <bits/stdc++.h>
 3 #define iter ::iterator
 4 using namespace  std;
 5 typedef long long ll;
 6 typedef pair<ll,ll>P;
 7 #define pb push_back
 8 #define se second
 9 #define fi first
10 #define rs o*2+1
11 #define ls o*2
12 const int N=2e5+5;
13 int n,m;
14 int maxv[N*4];
15 void build(int o,int l,int r){
16     if(l==r){
17         scanf("%d",&maxv[o]);
18         return;
19     }
20     int m=(l+r)/2;
21     build(ls,l,m);
22     build(rs,m+1,r);
23     maxv[o]=max(maxv[ls],maxv[rs]);
24 }
25 void up(int o,int l,int r,int p,int v){
26     if(l==r&&l==p){
27         maxv[o]=v;
28         return;
29     }
30     int m=(l+r)/2;
31     if(p<=m)up(ls,l,m,p,v);
32     else up(rs,m+1,r,p,v);
33     maxv[o]=max(maxv[ls],maxv[rs]);
34 }
35 int query(int o,int l,int r,int ql,int qr){
36     if(l>=ql&&r<=qr){
37         return maxv[o];
38     }
39     int m=(l+r)/2;
40     int res=0;
41     if(ql<=m)res=max(res,query(ls,l,m,ql,qr));
42     if(qr>m)res=max(res,query(rs,m+1,r,ql,qr));
43     return res;
44 }
45 int main(){
46     while(~scanf("%d%d",&n,&m)){
47         build(1,1,n);
48         while(m--){
49             char s[10];
50             int x,y;
51             scanf("%s",s);
52             if(s[0]=='Q'){
53                 scanf("%d%d",&x,&y);
54                 if(x>y)swap(x,y);
55                 printf("%d
",query(1,1,n,x,y));
56             }
57             else{
58                 scanf("%d%d",&x,&y);
59                 up(1,1,n,x,y);
60             }
61         }
62     }
63 }