hdu1754 I Hate It 线段树RMQ

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 2e5+10;
17 
18 int mx[maxn<<2];
19 
20 void pushup(int rt){
21     mx[rt] = max(mx[rt<<1],mx[rt<<1|1]);
22 }
23 
24 void build(int l,int r,int rt){
25     if(l == r){
26         scanf("%d",&mx[rt]);
27         return ;
28     }   
29     int mid = (l+r)/2;
30     build(l,mid,rt<<1);
31     build(mid+1,r,rt<<1|1);
32     pushup(rt);
33 }
34 
35 void update(int l,int r,int rt,int p,int va){
36     if(l == r){
37         mx[rt] = va;
38         return ;
39     }
40     int mid = (l+r)/2;
41     if(p<=mid) update(l,mid,rt<<1,p,va);
42     else update(mid+1,r,rt<<1|1,p,va);
43     pushup(rt);
44 }
45 
46 int query(int l,int r,int rt,int L,int R){
47     if(L<=l && r<=R){
48         return mx[rt];
49     }
50 
51     int mid = (l+r)/2;
52     if(L>mid)
53         return query(mid+1,r,rt<<1|1,L,R);
54     if(R<=mid)
55         return query(l,mid,rt<<1,L,R);
56     return max(query(l,mid,rt<<1,L,R),query(mid+1,r,rt<<1|1,L,R));
57 }
58 
59 int main(){
60     int n,m;
61     while(scanf("%d%d",&n,&m) != EOF){
62         build(1,n,1);
63         for(int i=0; i<m; i++){
64             char op; int a,b;
65             cin >> op >> a >> b;
66             if(op == 'Q')
67                 cout << query(1,n,1,a,b) << endl;
68             else
69                 update(1,n,1,a,b);  
70         }
71     }
72 
73     return 0;
74 }