I Hate It

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

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

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
        
 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N=200000+5;
int t,n,m;
int tree[N<<2];
int a[N];
void PushUp(int rt){
    tree[rt] = tree[rt*2] + tree[rt*2+1]; ///区间和的更新操作
}
void MaxPushUp(int rt){
    tree[rt] =max(tree[rt*2] , tree[rt*2+1]) ; ///区间和的更新操作
}
void Build(int l,int r,int rt){
    // l,r 代表的是这个区间内的左端点 和 右端点， rt代表的是 [l,r] 这个区间内的值是存在哪一个位置的。
    if(l==r){
        //scanf("%d",&tree[rt]);
         tree[rt] = a[l];
        return;
    }
    int m=(l+r)/2;// 对于区间区分，我们一般将m点划入左半边区间
    Build(l,m,rt*2);
    Build(m+1,r,rt*2+1);
    MaxPushUp(rt); // PushUp 函数是通过2个子节点来更新现在这个节点的状态， 对于不同的要求需要不同的写法。

}
int SumQuery(int l,int r,int rt,int L,int R){// [L,R]为查询区间
    if(L<=l&&r<=R){
        return tree[rt];// 如果成立则满足查询区间覆盖了当前区间， 直接返回当前区间的值
    }
    int m=(l+r)/2;
    int res=0;
     if(L<=m)    res+=SumQuery(l,m,rt*2,L,R);//左边有一部分需要查询的区域。
    if(m<R)     res+=SumQuery(m+1,r,rt*2+1,L,R);//右边有一部分。
    return res;

}
int MaxQuery(int l,int r,int rt,int L,int R){// [L,R]为查询区间
    if(L<=l&&r<=R){
        return tree[rt];// 如果成立则满足查询区间覆盖了当前区间， 直接返回当前区间的值
    }
    int m=(l+r)/2;
    int res=-INF;
    if(L<=m)    res=max(res,MaxQuery(l,m,rt*2,L,R));//左边有一部分需要查询的区域。
    if(m<R)     res=max(res,MaxQuery(m+1,r,rt*2+1,L,R));//右边有一部分。
    return res;

}
void AddUpdata(int l,int r,int rt,int L,int C){// l,r,rt 与前面的定义一样， L代表的是要更新区间的位置，C代表的是修改后的值
    if(l==r){// 这里不能写成 if(l == L) 因为有可能左端点恰好是要更新的位置， 但是还有右端点， 我们直接更新的只有区间 [L,L]。
        tree[rt]+=C;
        return ;
    }
    int m=(l+r)/2;
    if(L<=m) AddUpdata(l,m,rt*2,L,C);//要更新的区间在左边部分，所以往左边走，更新左边
    else AddUpdata(m+1,r,rt*2+1,L,C);//要更新的区间在右边部分， 往右边走，更新右边
    PushUp(rt);//更新完子节点之后需要更新现在的位置， 需要保证线段树的性质。
}
void Updata(int l,int r,int rt,int L,int C){// l,r,rt 与前面的定义一样， L代表的是要更新区间的位置，C代表的是修改后的值
    if(l==r){// 这里不能写成 if(l == L) 因为有可能左端点恰好是要更新的位置， 但是还有右端点， 我们直接更新的只有区间 [L,L]。
        tree[rt]=C;
        return ;
    }
    int m=(l+r)/2;
    if(L<=m) Updata(l,m,rt*2,L,C);//要更新的区间在左边部分，所以往左边走，更新左边
    else Updata(m+1,r,rt*2+1,L,C);//要更新的区间在右边部分， 往右边走，更新右边
    MaxPushUp(rt);//更新完子节点之后需要更新现在的位置， 需要保证线段树的性质。
}
int main()
{

    while(scanf("%d%d",&n,&m)!=EOF){
        ;
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        Build(1,n,1);
        char tmp[10];
        int i,j;

        while(m--){
            scanf("%s",tmp);
            scanf("%d%d",&i,&j);
            if(strcmp(tmp,"U")==0){
                Updata(1,n,1,i,j);
            }
            if(strcmp(tmp,"Q")==0){
                printf("%d\n",MaxQuery(1,n,1,i,j));
            }

        }

    }
    //cout << "Hello world!" << endl;
    return 0;
}