Input
本題目包含多組測試，請處理到檔案結束。
在每個測試的第一行，有兩個正整數 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表學生的數目和操作的數目。
學生ID編号分别從1編到N。
第二行包含N個整數，代表這N個學生的初始成績，其中第i個數代表ID為i的學生的成績。
接下來有M行。每一行有一個字元 C (隻取'Q'或'U') ，和兩個正整數A，B。
當C為'Q'的時候，表示這是一條詢問操作，它詢問ID從A到B(包括A,B)的學生當中，成績最高的是多少。
當C為'U'的時候，表示這是一條更新操作，要求把ID為A的學生的成績更改為B。
Output
對于每一次詢問操作，在一行裡面輸出最高成績。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
http://acm.hdu.edu.cn/showproblem.php?pid=1754
View Code
1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 #define N 200000
5 #define max(a,b) ((a)>(b)? (a):(b))
6 struct node
7 {
8 int l,r;
9 int mx;
10 }tree[3*N];
11 void build(int l,int r,int i)
12 {
13 tree[i].l=l;tree[i].r=r;
14 if(l==r)
15 {
16 scanf("%d",&tree[i].mx);
17 return ;
18 }
19 int mid=(l+r)>>1;
20 build(l,mid,i<<1);
21 build(mid+1,r,i<<1|1);
22 tree[i].mx=max(tree[i<<1].mx,tree[i<<1|1].mx);
23 }
24 int query(int l,int r,int i)
25 {
26 if(l<=tree[i].l&&tree[i].r<=r) return tree[i].mx;
27 int temp,ans=0,mid=tree[i<<1].r;
28 if(l<=mid) {temp=query(l,r,i<<1);ans=max(ans,temp);}
29 if(r>mid) {temp=query(l,r,i<<1|1);ans=max(ans,temp);}
30 return ans;
31 }
32 void update(int k,int num,int i)
33 {
34 if(tree[i].l==tree[i].r) {tree[i].mx=num;return;}
35 if(k<=tree[i<<1].r) update(k,num,i<<1);
36 else update(k,num,i<<1|1);
37 tree[i].mx=max(tree[i<<1].mx,tree[i<<1|1].mx);
38 }
39 int main()
40 {
41 int n,m;
42 while(cin>>n>>m)
43 {
44 build(1,n,1);
45 while(m--)
46 {
47 char ch[3];int a,b;
48 scanf("%s%d%d",ch,&a,&b);
49 if(ch[0]=='Q') printf("%d\n",query(a,b,1));
50 else update(a,b,1);
51 }
52 }
53 return 0;
54 }