作的数目。
学生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
92014年10月6日 Problem - 1754
http://acm.hdu.edu.cn/showproblem.php?pid=1754 2/2
Hint
Huge input,the C function scanf() will work better than cin
Author
linle
Source
2007省赛集训队练习赛（6）_linle专场
?
?
?
?
?
?
题意：单点修改， 求区间最值。
?
?
解题思路：很明显，这题树状数组和线段树都能做，这里先用线段树搞吧，树状数组的也不难，只要把update和sum改一下就行了，就不给具体代码了。这题也是基本的线段树的应用，只要把单点修改，区间求和的update和query稍微改一下就行了。详见代码
?
线段树基础知识详见：线段树之入门篇
?
?
AC代码：
?
#include
#include
using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 222222; int MAX[maxn<<2]; void PushUP(int rt) { //这个也变成了两者的最大值，而不是求和了 MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]); // rt<<1|1 是 rt*2+1 的意思 } void build(int l,int r,int rt) { if (l == r) { scanf(%d,&MAX[rt]); return ; } int m = (l + r) >> 1; build(lson); build(rson); PushUP(rt); } void update(int p,int sc,int l,int r,int rt) { if (l == r) { MAX[rt] = sc; return ; } int m = (l + r) >> 1; if (p <= m) update(p , sc , lson); else update(p , sc , rson); PushUP(rt); } int query(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return MAX[rt]; } int m = (l + r) >> 1; int ret = 0; if (L <= m) ret = max(ret , query(L , R , lson)); //这里变成了求两者的最大值 if (R > m) ret = max(ret , query(L , R , rson)); return ret; } int main() { int n , m; while (~scanf(%d%d,&n,&m)) { build(1 , n , 1); while (m --) { char op[2]; int a , b; scanf(%s%d%d,op,&a,&b); if (op[0] == 'Q') printf(%d ,query(a , b , 1 , n , 1)); else update(a , b , 1 , n , 1); } } return 0; }
?
?