http://acm.hdu.edu.cn/showproblem.php?pid=1754
线段树，单点更新
1 #include <stdio.h> 2 3 #define lson l, m, root<<1 4 #define rson m+1, r, root<<1|1 5 6 const int maxn = 200010; 7 const int minint = 1<<31; 8 int max1[maxn<<2]; 9 10 int max(int x, int y) 11 { 12 return x>y? x: y; 13 } 14 15 void push_up(int root) 16 { 17 max1[root] = max(max1[root<<1], max1[root<<1|1]); 18 } 19 20 void build(int l, int r, int root) 21 { 22 int m; 23 if(l == r) 24 { 25 scanf("%d", max1+root); 26 return; 27 } 28 m = (l + r) >> 1; 29 build(lson); 30 build(rson); 31 push_up(root); 32 } 33 34 void update(int x, int change, int l, int r, int root) 35 { 36 int m; 37 if(l == r) 38 { 39 max1[root] = change; 40 return; 41 } 42 m = (l + r) >> 1; 43 if(x <= m) 44 { 45 update(x, change, lson); 46 } 47 if(m+1 <= x) 48 { 49 update(x, change, rson); 50 } 51 push_up(root); 52 } 53 54 int query(int L, int R, int l, int r, int root) 55 { 56 int m, result; 57 if(L <= l && r <= R) 58 { 59 return max1[root]; 60 } 61 result = minint; 62 m = (l + r) >> 1; 63 if(L <= m) 64 { 65 result = max(result, query(L, R, lson)); 66 } 67 if(m+1 <= R) 68 { 69 result = max(result, query(L, R, rson)); 70 } 71 return result; 72 } 73 74 int main() 75 { 76 int n, m, a, b; 77 char c; 78 while(~scanf("%d%d", &n, &m)) 79 { 80 build(1, n, 1); 81 getchar(); 82 while(m-- && scanf("%c%d%d%*c", &c, &a, &b)) 83 { 84 if(c == 'Q') 85 { 86 printf("%d\n", query(a, b, 1, n, 1)); 87 continue; 88 } 89 update(a, b, 1, n, 1); 90 } 91 } 92 return 0; 93 }