hdu 1754 I Hate It

http://acm.hdu.edu.cn/showproblem.php?pid=1754
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define maxn 300000
  5 using namespace std;
  6 
  7 int a[maxn];
  8 int max2;
  9 struct node
 10 {
 11     int l,r,max1;
 12 }tree[maxn*4];
 13 
 14 
 15 void build(int i,int l,int r)
 16 {
 17     tree[i].l=l;
 18     tree[i].r=r;
 19     if(l==r)
 20     {
 21         tree[i].max1=a[l];
 22         return;
 23     }
 24     int mid=(l+r)>>1;
 25     build(i<<1,l,mid);
 26     build(i<<1|1,mid+1,r);
 27     tree[i].max1=max(tree[i<<1].max1,tree[i<<1|1].max1);
 28 }
 29 
 30 void update(int i,int idx,int key)
 31 {
 32     if(tree[i].l==tree[i].r)
 33     {
 34         tree[i].max1=key;
 35         return ;
 36     }
 37     int mid=(tree[i].l+tree[i].r)>>1;
 38     if(idx<=mid)
 39     {
 40          update(i<<1,idx,key);
 41     }
 42     else
 43         update(i<<1|1,idx,key);
 44     tree[i].max1=max(tree[i<<1].max1,tree[i<<1|1].max1);
 45 }
 46 
 47 void search1(int i,int l,int r)
 48 {
 49     if(tree[i].l==l&&tree[i].r==r)
 50     {
 51         max2=max(max2,tree[i].max1);
 52         return ;
 53     }
 54     int mid=(tree[i].l+tree[i].r)>>1;
 55     if(r<=mid)
 56     {
 57         search1(i<<1,l,r);
 58     }
 59     else if(l>mid)
 60     {
 61         search1(i<<1|1,l,r);
 62     }
 63     else
 64     {
 65         search1(i<<1,l,mid);
 66         search1(i<<1|1,mid+1,r);
 67     }
 68 }
 69 
 70 
 71 int main()
 72 {
 73     int N,M;
 74     while(scanf("%d%d",&N,&M)!=EOF)
 75     {
 76         for(int i=1; i<=N; i++)
 77         {
 78             scanf("%d",&a[i]);
 79         }
 80         getchar();
 81         build(1,1,N);
 82         for(int i=1; i<=M; i++)
 83         {
 84             char ch;
 85             int a,b;
 86             scanf("%c %d%d",&ch,&a,&b);
 87             getchar();
 88             if(ch=='Q')
 89             {
 90                 max2=-1;
 91                 search1(1,a,b);
 92                 printf("%d
",max2);
 93             }
 94             else if(ch=='U')
 95             {
 96                 update(1,a,b);
 97             }
 98         }
 99     }
100     return 0;
101 }
View Code