I Hate It

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 37939 Accepted Submission(s): 15015

Problem Description 很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
Input 本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0 学生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

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
       ; }

HDU 1754 I Hate It (线段树)

I Hate It