HDU-I Hate It-1754 线段树

 1 #include<stdio.h>
 2 int tree[200000*4];
 3 int max(int a,int b)
 4 {
 5     return a>b?a:b;
 6 }
 7 void bulid(int t,int l,int r) //建树 
 8 {
 9     int n;
10     if(l==r)
11     {
12         scanf("%d",&tree[t]);
13         return ;
14     }
15     int mid=(l+r)>>1;
16     bulid(t*2,l,mid);
17     bulid(t*2+1,mid+1,r);
18     tree[t]=max(tree[t*2],tree[t*2+1]);
19     
20 }
21 void ge(int t,int l,int r,int x,int y) //更新区域值 
22 {
23     if(l==r)
24     {
25         tree[t]=y;
26         return ; 
27     }
28     int mid=(l+r)>>1;
29     if(x<=mid) 
30         ge(t*2,l,mid,x,y);
31     else 
32         ge(t*2+1,mid+1,r,x,y);
33     tree[t]=max(tree[t*2],tree[t*2+1]);
34     
35 }
36 int maxi(int t,int l,int r,int x,int y) //需找区间最大值 
37 {
38     int sum=0;
39 
40     if(x<=l&&r<=y)
41     {
42         return tree[t];
43     }
44 
45 
46         int mid=(l+r)>>1;
47         if(x<=mid)
48         {
49             sum=max(sum,maxi(t*2,l,mid,x,y));
50         }
51         if(y>mid)
52         {
53             sum=max(sum,maxi(t*2+1,mid+1,r,x,y));
54         }
55         
56         
57     return sum;
58         
59 }
60 int main()
61 {
62     int n,m,i,j,k,l,x,y;
63     char a[10];
64     while(scanf("%d%d",&n,&m)!=EOF)
65     {
66         bulid(1,1,n);
67         while(m--)
68         {
69             scanf("%s",a);
70             scanf("%d%d",&x,&y);
71             if(a[0]==‘U‘)
72             {
73                 ge(1,1,n,x,y);
74             }
75             else 
76             if(a[0]==‘Q‘)
77             {
78                 printf("%d\n",maxi(1,1,n,x,y));
79             }
80         }
81     }
82     return 0;
83 }