Problem Description

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

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

 

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

 

 

Author

linle

 

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int LEN = ;

 struct line

 {

     int left;

     int right;

     int ma;

 }line[LEN*];

 void buildt(int l, int r, int step)  //建树，同时初始化区间最值

 {

     line[step].left = l;

     line[step].right = r;

     line[step].ma = ;

     if (l == r)

         return;

     int mid = (l + r) / ;

     buildt(l, mid, step*);

     buildt(mid+, r, step*+);

 }

 int update(int l, int r, int value, int step)  //更新函数，返回整型

 {

     if (line[step].left == line[step].right){  //如果到达最深处的节点，则说明找到了需要更新的单点，赋值

         line[step].ma = value;

         return max(line[step/*].ma, line[step/*+].ma); //返回该节点与其兄弟节点的较大值

     }

     int mid = (line[step].left + line[step].right) / ;  //向下继续搜索

     if (r <= mid)

         line[step].ma = update(l, r, value, step*);

     else if (l > mid)

         line[step].ma = update(l, r, value, step*+);

     else{             //如果目标线段处于目前线段的中点的两边，则同时搜索该节点的两个子节点，并取较大值

         line[step].ma = max(update(l, mid, value, step*), update(mid+, r, value, step*+));

     }

     return max(line[step/*].ma, line[step/*+].ma);  //返回该节点与其兄弟节点的较大值

 }

 int dfs(int l, int r, int step)  //dfs找答案

 {

     if (l == line[step].left && r == line[step].right) //如果找到目标区间，返回值

         return line[step].ma;

     int mid = (line[step].left + line[step].right) / ;

     if (r <= mid)

         return dfs(l, r, step*);

     else if (l > mid)

         return dfs(l, r, step*+);

     else{

         return max(dfs(l, mid, step*), dfs(mid+, r, step*+)); //返回该节点与其兄弟节点的较大值

     }

 }

 int main()

 {

     int n, m;

     //freopen("in.txt", "r", stdin);

     while(scanf("%d %d", &n, &m) != EOF){

         buildt(, n, );

         for(int i = ; i <= n; i++){

             int t;

             scanf("%d", &t);

             update(i, i, t, );

         }

         for(int i = ; i < m; i++){

             char query[];

             int a, b;

             scanf("%s %d %d", query, &a, &b);

             if (query[] == 'U')

                 update(a, a, b, );

             else if (query[] == 'Q'){

                 printf("%d\n", dfs(a, b, ));

             }

         }

     }

     return ;

 }