KGSS - Maximum Sum

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

int arr[100005];
pair<int,int> tree[500005];
int n,q;

pair<int,int> _merge(pair<int,int> p1, pair<int,int> p2) {
    int a[4];
    a[0] = p1.first;
    a[1] = p1.second;
    a[2] = p2.first;
    a[3] = p2.second;
    int mx = -1;
    int mn = -1;
    for(int i = 0; i < 4; i++) {
        if(a[i] != -1) {
            if(mx == -1 || arr[mx] < arr[a[i]]) {
                mx = a[i];
            }
        }
    }
    for(int i = 0; i < 4; i++) {
        if(a[i] != -1 && a[i] != mx) {
            if(mn == -1 || arr[mn] < arr[a[i]]) {
                mn = a[i];
            }
        }
    }
    return {mx,mn};
}

void build(int l = 0, int r = n-1, int p = 1) {
    if(l == r) {
        tree[p] = {l,-1};
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    tree[p] = _merge(tree[p*2],tree[p*2+1]);
}

void update(int qt, int v, int l = 0, int r = n-1, int p = 1) {
    if(l == r) {
        arr[l] = v;
        tree[p] = {l,-1};
        return;
    }
    int mid = (l+r)/2;
    if(qt <= mid) {
        update(qt,v,l,mid,p*2);
    }
    else {
        update(qt,v,mid+1,r,p*2+1);
    }
    tree[p] = _merge(tree[p*2],tree[p*2+1]);
}

pair<int,int> query(int ql, int qr, int l = 0, int r = n-1, int p = 1) {
    if(l > qr || r < ql) {
        return {-1,-1};
    }
    if(l >= ql && r <= qr) {
        return tree[p];
    }
    int mid = (l+r)/2;
    return _merge(query(ql,qr,l,mid,p*2),query(ql,qr,mid+1,r,p*2+1));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    build();
    cin >> q;
    while(q--) {
        char c;
        int a,b;
        cin >> c >> a >> b;
        if(c == 'Q') {
            pair<int,int> res = query(a-1,b-1);
            //cout << "res is " << res.first << " " << res.second << "\n";
            int sum = arr[res.first] + (res.second == -1 ? 0:arr[res.second]);
            cout << sum << "\n";
        }
        else {
            update(a-1,b);
        }
    }
    return 0;
}