#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 0X3f3f3f3f
const ll MAXN = 2e5 + ;
const ll MOD = 1e9 + ;
ll a[MAXN];
struct node
{
int left, right; //区间端点
ll max, sum; //看题目要求
ll lazy;
void update(ll x)
{
sum += (right - left + ) * x;
lazy += x;
}
} tree[MAXN << ];
//建树，开四倍
void push_up(int x)
{
tree[x].sum = tree[x << ].sum + tree[x << | ].sum;
tree[x].max = max(tree[x << ].max, tree[x << | ].max);
}
void push_down(int x)
{
ll lazeval = tree[x].lazy;
if (lazeval)
{
tree[x << ].update(lazeval);
tree[x << | ].update(lazeval);
tree[x].lazy = ;
}
}
//若原数组从a[1]~a[n]，调用build(1,1,n);
void build(int x, int l, int r)
{
tree[x].left = l;
tree[x].right = r;
tree[x].sum = tree[x].lazy = ;
if (l == r) //若到达叶节点
{
tree[x].sum = a[l]; //存储A数组的值
tree[x].max = a[l];
}
else
{
int mid = (l + r) / ;
build(x << , l, mid);
build(x << | , mid + , r);
push_up(x);
}
return;
}
//update(1,l,r,v)
void update(int x, int l, int r, ll v) //区间更新
{
int L = tree[x].left, R = tree[x].right;
if (l <= L && R <= r)
{
tree[x].update(v);
tree[x].max += v;
}
else
{
push_down(x);
int mid = (L + R) / ;
if (mid >= l)
update(x << , l, r, v);
if (r > mid)
update(x << | , l, r, v);
push_up(x);
}
}
//单点更新,更新pos点，调用add(1,pos,v)
void add(int x, int pos, ll v) //当前更新的节点的编号为id（一般是以1为第一个编号）。pos为需要更新的点的位置，v为修改的值的大小
{ int L = tree[x].left, R = tree[x].right;
if (L == pos && R == pos) //左右端点均和pos相等，说明找到了pos所在的叶子节点
{
tree[x].sum += v;
tree[x].max += v;
return; //找到了叶子节点就不需要在向下寻找了
}
int mid = (L + R) / ;
if (pos <= mid)
add(x << , pos, v);
else
add(x << | , pos, v); //寻找k所在的子区间
push_up(x); //向上更新
}
//调用query_sum（1,l,r)即可查询[l,r]区间内元素的总和
//区间查询
ll query_sum(int x, int l, int r)
{
int L = tree[x].left, R = tree[x].right;
if (l <= L && R <= r)
return tree[x].sum;
else
{
push_down(x);
ll ans = ;
int mid = (L + R) / ;
if (mid >= l)
ans += query_sum(x << , l, r);
if (r > mid)
ans += query_sum(x << | , l, r);
push_up(x);
return ans;
}
}
//调用query_max(1,l,r)即可求[l,r]区间内元素的最大值
ll query_max(int x, int l, int r)
{
int L = tree[x].left, R = tree[x].right;
if (l == L && R == r)
return tree[x].max;
else
{
push_down(x);
int mid = (L + R) / ;
if (r <= mid)
return query_max(x << , l, r);
else if (l > mid)
return query_max(x << | , l, r);
else
return max(query_max(x << , l, mid), query_max(x << | , mid+, r));
}
}
int main()
{
ll n, m;
while (scanf("%lld%lld", &n, &m) != EOF)
{
for (int i = ; i <= n; i++)
scanf("%lld", &a[i]);
build(, , n);
getchar();
while (m--)
{
int l, r;
char que;
scanf("%c %d %d", &que, &l, &r);
getchar();
if (que == 'Q')
printf("%lld\n", query_max(, l, r));
else if (que == 'U')
update(, l,l, r - a[l]),a[l]=r;
}
}
return ;
}