hdu1754I Hate It

http://acm.hdu.edu.cn/showproblem.php?pid=1754
依次比较左右子节点父节点存最大值
View Code
 1  #include <iostream>
 2  #include<cstdio>
 3  #include<string.h>
 4  #define MAX 200000
 5  using namespace std;
 6  int s[MAX*4],a;
 7  void push(int w)
 8  {
 9      if(s[2*w]>s[2*w+1])
10      s[w] = s[2*w];
11      else
12      s[w] = s[2*w+1];
13  }
14  void build(int l,int r,int w)
15  {
16      if(l==r)
17      {
18          scanf("%d",&a);
19          s[w] = a;
20          return ;
21      }
22      int m = (l+r)/2;
23      build(l,m,2*w);
24      build(m+1,r,2*w+1);
25      push(w);
26  }
27  void add(int p,int da,int l,int r,int w)
28  {
29      if(l==r)
30      {
31          s[w] = da;
32          return;
33      }
34      int m = (l+r)/2;
35      if(p<=m)
36      add(p,da,l,m,2*w);
37      else
38      add(p,da,m+1,r,2*w+1);
39      push(w);
40  }
41  int search(int a,int b,int l,int r,int w)
42  {
43      if(a<=l&&b>=r)
44      {
45         return s[w];
46      }
47      int m = (l+r)/2,re = 0;
48      if(a<=m)
49      re = max(re,search(a,b,l,m,2*w));
50      if(b>m)
51      re = max(re,search(a,b,m+1,r,2*w+1));
52      return re;
53  }
54  int main()
55  {
56      int i,j,k1,k2,n,m;
57      char c;
58      while(scanf("%d%d",&n,&m)!=EOF)
59      {
60          build(1,n,1);
61          while(m--)
62          {
63              scanf("%*c%c",&c);
64              if(c=='Q')
65              {
66                  scanf("%d %d",&k1,&k2);
67                  printf("%d\n",search(k1,k2,1,n,1));
68              }
69              else
70              {
71                  scanf("%d %d",&k1,&k2);
72                  add(k1,k2,1,n,1);
73              }
74          }
75      }
76      return 0;
77  }