http://acm.hdu.edu.cn/showproblem.php?pid=1754
简单线段树题，单点更新+区间求最大值。
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 const int N=200002; 6 int a[N],ans = 0; 7 struct node 8 { 9 int l,r; 10 int Max; 11 } tree[4*N]; 12 void build(int root,int l,int r) 13 { 14 tree[root].l = l; 15 tree[root].r = r; 16 if (l==r) 17 { 18 tree[root].Max = a[r]; 19 return ; 20 } 21 int mid = (l+r)>>1; 22 build(root<<1,l,mid); 23 build(root<<1|1,mid+1,r); 24 tree[root].Max = max(tree[root<<1].Max,tree[root<<1|1].Max); 25 } 26 void Query(int t,int l,int r) 27 { 28 if (l <=tree[t].l && tree[t].r <= r) 29 { 30 ans = max(ans,tree[t].Max); 31 return ; 32 } 33 int mid = (tree[t].l+tree[t].r)>>1; 34 if (r <= mid) 35 Query(t<<1,l,r); 36 else if (l > mid) 37 Query(t<<1|1,l,r); 38 else 39 { 40 Query(t<<1,l,mid); 41 Query(t<<1|1,mid+1,r); 42 } 43 } 44 void update(int t,int l,int r,int key) 45 { 46 if (tree[t].l==l&&tree[t].r==r) 47 { 48 tree[t].Max = key; 49 return ; 50 } 51 int mid = (tree[t].l+tree[t].r)>>1; 52 if (l <= mid) 53 update(t<<1,l,r,key); 54 else 55 update(t<<1|1,l,r,key); 56 tree[t].Max = max(tree[t<<1].Max,tree[t<<1|1].Max); 57 } 58 int main() 59 { 60 int n,q; 61 char s[3]; 62 while(~scanf("%d%d",&n,&q)) 63 { 64 for (int i = 1; i <= n; i++) 65 scanf("%d%*c",&a[i]); 66 build(1,1,n); 67 while(q--) 68 { 69 int x,y; 70 ans = 0; 71 scanf("%s",s); 72 scanf("%d%d",&x,&y); 73 if (s[0]=='Q') 74 { 75 Query(1,x,y); 76 printf("%d ",ans); 77 } 78 else 79 update(1,x,x,y); 80 } 81 } 82 return 0; 83 }