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

Sample Output

Hint

Huge input,the C function scanf() will work better than cin

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
#define pq priority_queue<int>
#define pql priority_queue<ll>
#define pqn priority_queue<node>
#define v vector<int>
#define vl vector<ll>
#define lson rt<<1, l, m
#define rson rt<<1|1, m+1, r
#define read(x) scanf("%d",&x)
#define lread(x) scanf("%lld",&x);
#define pt(x) printf("%d
",(x))
#define yes printf("YES
");
#define no printf("NO
");
#define gcd __gcd
#define out(x) cout<<x<<endl;
#define over cout<<endl;
#define rep(j,k) for (int i = (int)(j); i <= (int)(k); i++)
#define input(k) for (int i = 1; i <= (int)(k); i++)  {cin>>a[i] ; }
#define mem(s,t) memset(s,t,sizeof(s))
#define re return ;
#define ok return 0;
#define TLE std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod(x) ((x)%9973)
#define test cout<<"     ++++++      "<<endl;
#define ls now<<1
#define rs now<<1|1
const int N=201000+100;
typedef struct node
{
    int val,l,r,sum,mx,mn,lazy;
    //int mid() {return (l+r)>>1;}
}node;
node dp[N*4];
int a[N],maxn;
void upsum(int now) {    dp[now].sum = dp[ls].sum+dp[rs].sum;    }
void upmx(int now)  {    dp[now].mx = max(dp[ls].mx,dp[rs].mx);  }
void build(int now,int l,int r)
{
    dp[now].l=l,dp[now].r=r;
    if(dp[now].l==dp[now].r)    {        dp[now].mx = a[l]; re ;    }
    int mid = (l+r)>>1;
    build(ls,l,mid);
    build(rs,1+mid,r);
    upmx(now);
}
void querymx(int now,int l,int r)
{
    if(dp[now].l>=l && dp[now].r<=r) {maxn = max(dp[now].mx,maxn);re;}
    int mid = (dp[now].l+dp[now].r)>>1;
    if(l<=mid)
        querymx(ls,l,r);
    if(r>mid)
        querymx(rs,l,r);

}
void upnode(int now,int l,int k)
{
    if(dp[now].l==dp[now].r&&dp[now].l==l)
    {
        dp[now].mx = k;
        re;
    }
    int mid =(dp[now].l+dp[now].r)>>1;
    if(l<=mid)
        upnode(ls,l,k);
    else
        upnode(rs,l,k);
    dp[now].mx=max(dp[ls].mx,dp[rs].mx);
}


int main()
{
    string str;int ll,rr,n,m;
    TLE;
    while(cin>>n>>m)
    {
        input(n);
        build(1,1,n);
        rep(1,m)
        {
            cin>>str>>ll>>rr;
            if(str[0]=='Q')
            {
                maxn = -1;
                querymx(1,ll,rr);
                cout<<maxn<<endl;
            }
            else
                upnode(1,ll,rr);
        }
    }
    ok;
}

所遇皆星河