hdu1754 I Hate It

树状数组学习参考博客：http://blog.csdn.net/u010598215/article/details/48206959

树状数组之前没看懂就放着一直没看了,现在抽空学下...

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstring>
 5 #define CLR(a,b) memset((a),(b),sizeof((a)))
 6 using namespace std;
 7 typedef long long ll;
 8 const int N = 200001;
 9 int n;
10 int a[N];
11 int tree[N];
12 int lowbit(int x){
13     return x&(-x);
14 }
15 void update(int pos){
16     int lx, i;
17     while(pos <= n){
18         tree[pos] = a[pos];
19         lx = lowbit(pos);
20         for(i = 1; i < lx; i <<= 1)
21             tree[pos] = max(tree[pos], tree[pos-i]);
22         pos += lowbit(i);
23     }
24 }
25 int query_ma(int x, int y){
26     int ma = 0;
27     while(y >= x){
28         ma = max(ma, a[y]);
29         y--;
30         for(; y - lowbit(y) >= x; y -= lowbit(y))
31             ma = max(tree[y], ma);
32     }
33     return ma;
34 }
35 int main(){
36     int m, i;
37     while(~scanf("%d%d", &n, &m)){
38         CLR(tree, 0);
39         for(i = 1; i <= n; ++i){
40             scanf("%d", &a[i]);
41             update(i);
42         }
43         int l, r;
44         char c;
45         while(m--){
46             scanf("%*c%c%d%d", &c, &l, &r);
47             if(c == 'Q')
48                 printf("%d
", query_ma(l,r));
49             else {
50                 a[l] = r;
51                 update(l);
52             }
53         }
54     }
55     return 0;
56 }

View Code