HDU 1754

第一题线段树，纪念一下
 1 #include <cstdio>
 2 #include <iostream>
 3 using namespace std;
 4 int  tree[800005];
 5 void build(int l,int r,int root){
 6     if(l==r){
 7         scanf("%d",&tree[root]);
 8     }
 9     else {
10         int mid=(l+r)/2;
11         build(l,mid,root*2);
12         build(mid+1,r,root*2+1);
13         tree[root]=max(tree[root*2],tree[root*2+1]);
14     }
15 }
16 void updata(int x,int y,int l,int r,int root){
17     if(l==r){
18         tree[root]=y;
19     }
20     else {
21         int mid=(l+r)/2;
22         if(x<=mid)updata(x,y,l,mid,root*2);
23         else updata(x,y,mid+1,r,root*2+1);
24         tree[root]=max(tree[root*2],tree[root*2+1]);
25     }
26 }
27 int query(int x,int y,int l,int r,int root){
28     if(x<=l&&y>=r){
29         return tree[root];
30     }
31     else {
32         int sum=0,mid=(l+r)/2;
33         if(x<=mid)sum=max(sum,query(x,y,l,mid,root*2));
34         if(y>mid)sum=max(sum,query(x,y,mid+1,r,root*2+1));
35         return sum;
36     }
37 }
38 int main(){
39 
40     int n,m,x,y;
41     char s[5];
42     while(scanf("%d%d",&n,&m)!=EOF){
43         build(1,n,1);
44         for(int i=0;i<m;i++){
45             scanf("%s%d%d",s,&x,&y);
46             if(s[0]=='U')updata(x,y,1,n,1);
47             else printf("%d
",query(x,y,1,n,1));
48         }
49     }
50     return 0;
51 }