HDU 1754

成段更新 easy
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 const int MM=200002;
 8 int num[MM<<2];
 9 void buildtree(int l,int r,int id)
10 {
11     if(l==r)
12     {
13         scanf("%d",&num[id]);return;
14     }
15     else
16     {
17         int mid=(l+r)>>1;
18         buildtree(l,mid,id<<1);
19         buildtree(mid+1,r,id<<1|1);
20         num[id]=max(num[id<<1],num[id<<1|1]);
21     }
22 }
23 int query(int L,int R,int l,int r,int id)
24 { 
25     int maxx=0x80000000;
26     if(L<=l&&r<=R)return num[id];
27     else
28     {
29         int mid=(l+r)>>1;
30         if(L<=mid)
31             maxx=max(query(L,R,l,mid,id<<1),maxx);
32         if(R>mid)
33             maxx=max(query(L,R,mid+1,r,id<<1|1),maxx);
34         return maxx;
35     }
36     
37 }
38 void update(int pos,int e,int l,int r,int id)
39 {
40     if(l==r)
41     {
42         num[id]=e;
43     }
44     else
45     {
46         int mid=(l+r)>>1;
47         if(pos<=mid)
48             update(pos,e,l,mid,id<<1);
49         else if(pos>mid)
50             update(pos,e,mid+1,r,id<<1|1);
51         num[id]=max(num[id<<1],num[id<<1|1]);
52     }
53 }
54 int main()
55 {
56     int t,n,cas,i,x,y;
57     char ch[2];
58     
59     while(~scanf("%d %d",&n,&t))
60     {
61         buildtree(1,n,1);
62         while(t--)
63         {
64             scanf("%s %d %d",ch,&x,&y);
65             if(ch[0]=='U')
66             {
67                 update(x,y,1,n,1);
68             }
69             else
70             {
71                 printf("%d
",query(x,y,1,n,1) );
72             }
73         }
74         
75     }
76     return 0;
77 }