学生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
HintHuge input,the C function scanf() will work better than cin
Author linle
Source 2007省赛集训队练习赛（6）_linle专场
Recommend lcy | We have carefully selected several similar problems for you: 1542 1394 2795 1540 1255
又是模拟超时要用线段树的题。不过还好，这只是个单点更改区间查询的题目，使用模板就是了。
如果对线段树不明白，就百度吧，因为构建子树的方法太强大了。
反正和树有关的大部分用到了二分查找的思想。
代码：500MS 因为是模板没怎么改，也就没优化了。
#include
#include
#include
using namespace std
; #define M 200001
int a
[M
]; int k
; struct Node
{ int left
; int right
; int num
; }node
[M
<<2
]; void MakeTree
(int l
,int r
,int i
) //建树。 { node
[i
].left
=l
; node
[i
].right
=r
; if(l
==r
) //找到一个最低层节点，这个是度为0的点，不会有子树。 { node
[i
].num
=a
[l
]; return ; } int m
=(l
+r
)/2
; MakeTree
(l
,m
,2
*i
); //构建左子树。 MakeTree
(m
+1
,r
,2
*i
+1
); //构建右子树。 node
[i
].num
=max
(node
[i
*2
].num
,node
[i
*2
+1
].num
); //节点的值是两个子树的最大值。 } void UpdateTree
(int x
,int i
) //更改某一点的值，也就是更新。 { int l
=node
[i
].left
; int r
=node
[i
].right
; if(x
==r
&& x
==l
) { node
[i
].num
=k
; //单点更新的好处：这个节点一定是最下面一层的点。不用考虑子树。 return; } int m
=(l
+r
)/2
; if(x
>m
) UpdateTree
(x
,2
*i
+1
); else UpdateTree
(x
,2
*i
); node
[i
].num
=max
(node
[i
*2
].num
,node
[i
*2
+1
].num
); //父节点的值都在回溯到这里时被更新了。 } int QueryTree
(int x
,int y
,int i
) //查找区间的最值。 { int l
=node
[i
].left
; int r
=node
[i
].right
; if(x
==l
&& y
==r
) { return node
[i
].num
; //如果查找区间刚好是这个节点所代表的区间，就直接返回该点的值。 } int m
=(l
+r
)/2
; if(x
>m
) return QueryTree
(x
,y
,2
*i
+1
); //如果查找区间的左边界比中间值大，查找区间在右子树里面。 else if(y
<=m
) return QueryTree
(x
,y
,2
*i
); //如果查找区间的右边界比中间值小，查找区间在左子树里面。 else //否则查找区间被中间值分成两部分，一部分：x->m,一部分:m+1->y. return max
(QueryTree
(x
,m
,2
*i
),QueryTree
(m
+1
,y
,2
*i
+1
)); } int main() { int n
,m
,i
,j
,x
,y
; char c
[10
]; while(scanf
("%d%d"
,&n
,&m
)!=EOF
) { // memset(node,0,sizeof node);
for(i
=1
;i
<=n
;i
++) scanf
("%d"
,&a
[i
]); MakeTree
(1
,n
,1
); //建立一棵区间长度为1->n的树。 while(m
--) { scanf
("%s%d%d"
,c
,&x
,&y
); if(c
[0
]=='Q'
) printf
("%d\n"
,QueryTree
(x
,y
,1
)); else if(c
[0
]=='U'
) { k
=y
; UpdateTree
(x
,1
); } } } return 0
; }