# B - I Hate It

Input

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

#include <bits/stdc++.h>
using namespace std;
#define lson left,mid,root << 1
#define rson mid+1,right,root << 1 | 1

const int maxn = 2e5+100;

int sum[maxn << 2];

void pushup(int root)
{
sum[root] = max(sum[root << 1], sum[root << 1 | 1]);
}

void build(int left, int right, int root)
{
if(left == right)
{
scanf("%d",&sum[root]);
return;
}
int mid = left + right >> 1;
build(lson);
build(rson);
pushup(root);
}

void update(int left, int right , int root ,int target, int c)
{
if(left == right)
{
sum[root] = c;
return;
}
int mid = left + right >> 1;
if(target <= mid)
update(lson, target, c);
else
update(rson, target, c);
pushup(root);
}

int query(int left, int right, int root , int L, int R)
{
if(L <= left && right <= R)
{
return sum[root];
}
int mid = left + right >> 1;
int ans = 0;
if(L <= mid)
ans = max(ans, query(lson, L, R));
if(R > mid)
ans = max(ans, query(rson, L, R));
return ans;
}
int main()
{
int n, m;
while(~scanf("%d%d",&n,&m))
{
build(1, n, 1);
char op[2];
int l, r;
while(m--)
{
scanf("%s%d%d",op,&l,&r);
if(op[0] == 'U')
update(1, n, 1, l, r);
else
printf("%d\n",query(1, n, 1, l, r));
}
}
return 0;
}