RT

#include<bits/stdc++.h>
using namespace std;
struct tree 
{
    int l;//左子节点编号 
    int r;//右... 
    int w;//该点的值 
}d[1000010];
int a[1000010];
int h=1;
int n,m; 

void build(int s,int t,int me) {
  if (s==t) { //如果到底了，就记上 
    d[me].w=a[s];
    return;
  }

  int m=s+((t-s)>>1); 
  d[me].l=++h;//先记左节点 
  build(s,m,d[me].l);//递归建左子树 
  d[me].r=++h;//记右节点 
  build(m+1,t,d[me].r);//递归建右子树 
  d[me].w=max(d[d[me].l].w,d[d[me].r].w);//该点为左右节点的最大值 
}

int change(int l,int r,int u,int v,int me)
{
    //[l,r]表示你现在所在区间，你要把u点值改为v,me表示现在所在的点 
    if(l==u && r==u)
        {
            d[u].w=v;
            return d[u].w;
        }
    int m=l+((r-l)>>1);
    int k;
    if(m<u)//如果左子节点编号小于u,说明左子树节点都小于u 
    {
        k=change(m+1,r,u,v,d[me].r);//遍历右子树 
        k=max(d[me].l,k);//由于右子树值更新，所以重新比一遍 
    }
    else
    { 
        k=change(l,m,u,v,d[me].l);//否则遍历左子树 
        k=max(d[me].r,k); //... 
    } 
    d[me].w=k;
    return d[me].w;//返回该子节点的值，用于父节点比较 
}

int finding(int l, int r, int s, int t, int me) {
    //[l,r]表示你要找的区间，[s,t]表示现在所查的区间,me表示现在所在的点 
  if (l<=s && t<=r)
  { 
    return d[me].w;//到底了，就返回这个值 
  }
  int m=s+((t-s)>>1),sum=-90000;

  if(l<=m) 
    sum=max(sum,finding(l,r,s,m,d[me].l));//比较 
  if(r>m) 
    sum=max(sum,finding(l,r,m+1,t,d[me].r));//比较，防止左右端点都包括在内的情况 
  return sum;
}

int main()
{
    cin>>n>>m;
    for(register int i=1;i<=n;++i)//初始化 
        {
            d[i].l=d[i].r=-1;
            d[i].w=-1;
        }

    for(register int i=1;i<=n;++i)
        {
            cin>>a[i];
        }

    build(1,n,1);//建树

    for(register int i=1;i<=m;++i)
        {
            char x;
            cin>>x;
            int u,v;
            cin>>u>>v;
            if(x=='U')
            {
                change(1,n,u,v,1);
            }
            else 
            { 
                cout<<finding(u,v,1,n,1)<<endl;
            }
        }
    while(1);
    return 0;
}