hdu 1754

地址：http://acm.hdu.edu.cn/showproblem.php?pid=1754

题意：给n个数字。m次操作，每次操作更新一个数字或者查询区间最大值。

mark：典型线段树题。不过a的时候学了一下树状数组求区间最值。感觉对树状数组的理解又深刻了一点。不过这个更新不是O(lgn)而是O(lgn*lgn)的，比线段树慢！

代码：

线段树：

 1 # include <stdio.h>
 2 # include <string.h>
 3 
 4 
 5 #define max(a,b) (a>b?a:b)
 6 int n ;
 7 int tr[200010<<2] ;
 8 
 9 
10 void u(int a, int b, int l, int r, int rt)
11 {    
12     int m = (l+r)/2 ;
13     if (l == r) {
14         tr[rt] = b;
15         return;
16     }
17     if (a <= m) u(a, b, l, m, rt*2);
18     else u(a, b, m+1, r, rt*2+1);
19     tr[rt] = max(tr[rt*2], tr[rt*2+1]);
20 }
21 
22 
23 int q(int a, int b, int l, int r, int rt)
24 {
25     int m = (l + r) / 2, a1, a2 ;
26     if (a == l && b == r) return tr[rt];
27     if (b <= m) return q(a, b, l, m, rt*2) ;
28     else if (a > m) return q(a, b, m+1, r, rt*2+1) ;
29     a1 = q(a, m, l, m, rt*2), a2 = q(m+1, b, m+1, r, rt*2+1) ;
30     return max(a1, a2) ;
31 }
32 
33 
34 int main ()
35 {
36     int m, i, a, b ;
37     char op[5] ;
38     
39     while (~scanf ("%d%d", &n, &m))
40     {
41         //memset (tr, 0, sizeof(tr));
42         for (i = 1 ; i <= n ; i++)
43             scanf ("%d", &a), u(i, a, 1, n, 1);
44         while (m--)
45         {
46             scanf ("%s %d %d", op, &a, &b) ;
47             if (op[0] == 'U') u(a, b, 1, n, 1);
48             else printf ("%d
", q(a, b, 1, n, 1)) ;
49         }
50     }
51     return 0 ;
52 }

View Code

树状数组（不加inline优化max函数的话会TLE！！！）

 1 # include <stdio.h>
 2 # include <string.h>
 3 
 4 
 5 int n, num[200010], tr[200010];
 6 int lowbit(int x){return x & -x;}
 7 inline int max(int a, int b){return a>b?a:b;}
 8 
 9 
10 void u(int a, int b){
11     int i, j;
12     num[a] = b;
13     for (i = a; i <= n; i+=lowbit(i))
14     {
15         tr[i] = num[i];
16         for (j = 1; j < lowbit(i); j <<= 1)
17             tr[i] = max(tr[i], tr[i-j]);
18     }
19 }
20 
21 
22 int q(int a, int b){
23     int i = b, ans = num[b];
24     while (i >= a)
25         if (i-lowbit(i)+1 >= a)
26             ans = max(ans, tr[i]), i -= lowbit(i);
27         else
28             ans = max(ans, num[i]), i--;
29     return ans;
30 }
31 
32     
33 int main ()
34 {
35     int a, b, i, m;
36     char op[5];
37     while (~scanf ("%d%d", &n, &m))
38     {
39         memset(tr, 0, sizeof(tr));
40         for (i = 1; i <= n; i++)
41             scanf ("%d", &a), u(i, a);
42         while (m--)
43         {
44             scanf ("%s %d %d", op, &a, &b);
45             if (op[0] == 'U') u(a, b);
46             else printf ("%d
", q(a, b)) ;
47         }
48     }
49     return 0 ;
50 }

View Code