HDU1754
https://vjudge.net/contest/66989#problem/B
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
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
Hint
Huge input,the C function scanf() will work better than cin
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #define lson l,m,rt<<1 5 #define rson m+1,r,rt<<1|1 6 using namespace std; 7 const int maxn=200001; 8 int sum[maxn<<2]; 9 void pushup(int rt) 10 { 11 sum[rt]=max(sum[rt<<1],sum[rt<<1|1]); 12 } 13 /* 14 void pushdown(int rt,int ln,int rn) 15 { 16 if(add[rt]) 17 { 18 sum[rt<<1]+=add[rt]*ln; 19 sum[rt<<1|1]+=add[rt]*rn; 20 add[rt<<1]+=add[rt]; 21 add[rt<<1|1]+=add[rt]; 22 add[rt]=0; 23 } 24 } 25 */ 26 void build(int l,int r,int rt) 27 { 28 if(r==l) 29 { 30 scanf("%d",&sum[rt]); 31 return; 32 } 33 int m=(l+r)>>1; 34 build(lson); 35 build(rson); 36 pushup(rt); 37 } 38 void update(int L,int c,int l,int r,int rt) 39 { 40 if(l==r) 41 { 42 sum[rt]=c; 43 return; 44 } 45 int m=(l+r)>>1; 46 if(L<=m) 47 update(L,c,lson); 48 else 49 update(L,c,rson); 50 pushup(rt); 51 } 52 int query(int L,int R,int l,int r,int rt) 53 { 54 if(L<=l&&R>=r) 55 { 56 return sum[rt]; 57 } 58 int ans=0; 59 int m=(r+l)>>1; 60 if(L<=m) 61 ans=max(ans,query(L,R,lson)); 62 if(R>m) 63 ans=max(ans,query(L,R,rson)); 64 return ans; 65 } 66 int main() 67 { 68 ios::sync_with_stdio(false); 69 cin.tie(0); 70 int n,m,x,y; 71 char b; 72 while(~scanf("%d%d",&n,&m)) 73 { 74 build(1,n,1); 75 for(int i=1;i<=m;i++) 76 { 77 getchar(); 78 scanf("%c%d%d",&b,&x,&y); 79 if(b=='Q') 80 printf("%d\n",query(x,y,1,n,1)); 81 else 82 update(x,y,1,n,1); 83 } 84 } 85 return 0; 86 }
更多精彩
