https://www.luogu.com.cn/problem/P1531

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = l; i <= r; i++)
// #define int long long
using db = double;
using ll = long long;
using ull = unsigned long long;
const int INF = 1 << 30;
const long long INFL = 1LL << 60;
const int N = 2e5 + 23;
const int SN = 8e5 + 23;

int a[N], d[SN];

void build(int s, int t, int p)
{
    int lc = p * 2, rc = p * 2 + 1;
    if (s == t)
    {
        d[p] = a[s];
        return;
    }
    int mid = s + (t - s) / 2;
    build(s, mid, lc);
    build(mid + 1, t, rc);
    d[p] = max(d[lc], d[rc]);
}

void update(int l, int c, int s, int t, int p)
{
    int lc = p * 2, rc = p * 2 + 1;
    if (s == t)
    {
        d[p] = c;
        return;
    }
    int mid = s + (t - s) / 2;
    if (l <= mid)
        update(l, c, s, mid, lc);
    else
        update(l, c, mid + 1, t, rc);
    d[p] = max(d[lc], d[rc]);
}

int query(int l, int r, int s, int t, int p)
{
    int lc = 2 * p, rc = p * 2 + 1;
    if (l <= s && t <= r)
        return d[p];
    int mid = s + (t - s) / 2;
    int _max = -INF;
    if (l <= mid)
        _max = max(_max,
                   query(l, r, s, mid, lc));
    if (r > mid)
        _max = max(_max,
                   query(l, r, mid + 1, t, rc));
    return _max;
}

signed main()
{
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    rep(i, 1, n)
            cin >>a[i];
    build(1, n, 1);
    rep(i, 1, m)
    {
        char opt;
        int a1, b;
        cin >> opt >> a1 >> b;
        if (opt == 'Q')
            cout << query(a1, b, 1, n, 1) << endl;
        else
            update(a1, b, 1, n, 1);
    }
    return 0;
}

AC,WA,50pts