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

 

Sample Output

/*

hdu 1754 线段树(Max+单点修改)

U i j：在第i个上改为j

Q i j：求i到j的最大值

hhh-2016-02-27 14:20:36

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <ctime>

#include <algorithm>

#include <cmath>

#include <queue>

#include <map>

#include <vector>

typedef long long ll;

using namespace std;

const int maxn = 200000+5;

struct node

{

    int l,r;

    int Max;

} tree[maxn<<2];

void push_up(int r)

{

    int lson = r<<1,rson = (r<<1)|1;

    tree[r].Max = max(tree[lson].Max,tree[rson].Max);

}

void build(int i,int l,int r)

{

    tree[i].l = l,tree[i].r = r;

    tree[i].Max  = 0;

    if(l == r)

    {

        scanf("%d",&tree[i].Max);

        return ;

    }

    int mid = (l+r)>>1;

    build(i<<1,l,mid);

    build(i<<1|1,mid+1,r);

    push_up(i);

}

void push_down(int r)

{

}

void change(int i,int k,int c)

{

    if(tree[i].l == k && tree[i].r == k)

    {

        tree[i].Max = c;

        return ;

    }

    push_down(i);

    int mid = (tree[i].l + tree[i].r) >>1;

    if(k <= mid) change(i<<1,k,c);

    if(k > mid) change(i<<1|1,k,c);

    push_up(i);

}

int query(int i,int l,int r)

{

    if(tree[i].l >= l && tree[i].r <= r)

    {

        return tree[i].Max;

    }

    push_down(i);

    int mid = (tree[i].l+tree[i].r)>>1;

    int ans = 0;

    if(l <= mid) ans= max(ans,query(i<<1,l,r));

    if(r > mid) ans= max(ans,query(i<<1|1,l,r));

    return ans ;

}

int main()

{

    int T,n,m,cas = 1;

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

    {

        build(1,1,n);

//        printf("Case %d:\n",cas++);

        char op[10];

        int l,r;

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

        {

            scanf("%s",op);

            if(op[0] == 'Q')

            {

                scanf("%d%d",&l,&r);

                printf("%d\n",query(1,l,r));

            }

            else

            {

                scanf("%d%d",&l,&r);

                change(1,l,r);

            }

        }

    }

    return 0;

}