学步园

#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <ctime>
#define LL long long
#define Vi vector<int>
#define Si set<int>
#define readf freopen("input.txt","r",stdin)
#define writef freopen("output.txt","w",stdout)
#define FU(i,a) for(int i(1); i <= (a); i++)
#define FD(i,a) for(int i(a); i >= (1); i--)
#define FOR(i,a,b) for(int i(a);i <= (b); i++)
#define FORD(i,a,b) for(int i(a);i >= (b); i--)
#define SET(a,b) memset(a,b,sizeof(a))
#define SD(a) scanf("%d",&(a))
#define LN printf("\n")
#define PS printf(" ")
#define pb push_back
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
using namespace std;
const int maxn = 210000;
const int INF=99999999;
int value[maxn],N,M;


struct node{
    int a,b,max;
}tree[maxn<<2];// a为线段的左端点，b为右端点，sum即为这个怎么说....和！


void buildTree(int a,int b,int k){


    tree[k].a=a;
    tree[k].b=b;


    if(a==b){
        tree[k].max=value[a];
        return ;     //别忘记return ，太纠结了
    }


    int mid=(a+b)>>1;   //装B利器  位运算！ 其实就是除以2


    buildTree(a,mid,k<<1);   //装B利器  位运算！ 其实就是乘以2
    buildTree(mid+1,b,k<<1|1) ; //装B利器  位运算！ 其实就是乘以2+1;


    tree[k].max=max(tree[k<<1].max,tree[k<<1|1].max);   //先建树后统计，所以写在后面
}// k为根结点，a为左端点，b为右端点


void update(int a,int val,int k){
    int mid=(tree[k].a+tree[k].b)/2;
    int t=k<<1;


    if(tree[k].a==tree[k].b){
        tree[k].max=val;
        return ;
    }


    else if(a<=mid)
        update(a,val,t);
    else
        update(a,val,t+1);


    tree[k].max=max(tree[t].max,tree[t+1].max);
//不要忘记将所有父节点什么的更新
}//应该每次都从根节点开始找吧..~~


int query(int x,int y,int k){


    if(x <= tree[k].a && tree[k].b <= y)
    {
        return tree[k].max;   //如果区间将此段包含在内，直接返回
    }
    if( tree[k].a >y  || tree[k].b<x)
        return 0;




    int t1=-INF,t2=-INF;


    t1=query(x,y,k<<1);
    t2=query(x,y,k<<1|1);


    return (int)max(t1,t2);
}


void print(int k){


    printf("%d  %d   %d \n",tree[k].a,tree[k].b,tree[k].max);
    if(tree[k].a==tree[k].b)
        return ;
    print(k<<1);
    print(k<<1|1);
}
int main() {


    while(~scanf("%d%d",&N,&M))
    {
        memset(tree,0,sizeof(tree));
        FOR(i,1,N){
            SD(value[i]);
        }
        buildTree(1,N,1);
        char op[2];
        int num1,num2;
        FOR(i,1,M){
            scanf("%s",op);
            SD(num1);SD(num2);
            if(op[0]=='Q')
                printf("%d\n",query(num1,num2,1));
            else{
                update(num1,num2,1);
            }
        }


    }


    return 0;
}