Section Tree. index of maximum

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int,int>
#define pli pair <long long, int>
using namespace std;
using ll = long long;
using ld = long double;
void cv(vector <ll> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n\n";
}
ld n;
int N;
vector <ll> a;
int L,R;

int inter(int l, int r){
    //cout<<"LR= "<<L<<' '<<R<<'\n';
    //cout<<"lr= "<<l<<' '<<r<<'\n';
    if (l >= L && r <= R) {//cout<<"ONE\n";
            return 2;
    }
    else if (l < L && r >= L) {//cout<<"TWO\n";
            return 1;
    }
    else if (r > R && l <= R){//cout<<"THREE\n";
        return 1;
    }
    else return 0;
}
ll inf = pow(2, 63) - 100;
struct tree{
    vector <ll> tot;//sum
    vector <ll> MIN;
    vector <pli> MAX;
    void bld(){

        tot.assign(2*N-1,0);
        MIN.assign(2*N-1, inf);
        MAX.assign(2*N-1, {-inf, -1} );
        for (int i = 0; i < n; ++i){
            tot[N - 1 + i] = a[i];
            MIN[N - 1 + i] = a[i];
            MAX[N - 1 + i] = {a[i], i};
        }
        int id;
        for (int i = N * 2 - 2; i >= 2; i-=2){
            id = (i - 1) / 2;
            tot[id] = tot[i] + tot[i-1];
            MIN[id] = min(MIN[i], MIN[i-1]);
            if (MAX[i-1].first >= MAX[i].first) MAX[id] = MAX[i-1];
            else MAX[id] = MAX[i];
        }
    }
    void sh(){
        //cv(tot);
        //cv(MIN);
        for (int i = 0; i < MAX.size();++i){
            cout<<i<<' '<<MAX[i].first<<' '<<MAX[i].second<<'\n';
        }
    }
    ll getS(int l, int r, int id){
        //cout<<"id = "<<id<<"\n";
        int how = inter(l, r);
        //cout<<"how= "<<how<<'\n';
        if (how == 2) return tot[id];
        else if (how == 0) return 0;
        else{
            int m = (l + r) / 2;
            return getS(l, m, id*2+1) + getS(m+1, r, id*2+2);
        }
    }
    ll getMin(int l, int r, int id){
        int how = inter(l, r);
        if (how == 2) return MIN[id];
        else if (how == 0) return inf;
        else{
            int m = (l + r) / 2;
            return min(getMin(l, m, id*2+1) , getMin(m+1, r, id*2+2));
        }
    }
    pli getMax(int l, int r, int id){
        //cout<<"id= "<<id<<"\n";
        int how = inter(l, r);
        if (how == 2) return MAX[id];
        else if (how == 0) return {-inf, -1};
        else{
            int m = (l + r) / 2;
            pli a,b;
            a = getMax(l, m, id*2+1);
            b = getMax(m+1, r, id*2+2);
            if (a.first >= b.first) return a;
            else return b;
        }
    }
    void chg(int id){
        //cout<<"id = "<<id<<"\n";
        tot[id] = tot[id*2 + 1] + tot[id*2 + 2];
        MIN[id] = min(tot[id*2 + 1], tot[id*2 + 2]);
        if (MAX[id*2 + 1].first >= MAX[id*2 + 2].first){
            MAX[id] = MAX[id*2 + 1];
        }
        else MAX[id] = MAX[id*2 + 2];

        if (id == 0) return;
        chg( (id - 1) / 2);
    }
};

tree wrk;

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	N = pow(2, ceil(log2(n)));
	a.assign(n, 0);
	for (ll &x: a) cin>>x;
	wrk.bld();
	//wrk.sh();
	int m; cin>>m; char wht;
	pli res;
	for (int i=0;i<m;++i){
        cin>>wht;
        if (wht == 's') {
                cin>>L>>R;
            L--; R--;
            res = wrk.getMax(0, N-1, 0);
            cout<<res.second+1<<' ';
        }else{
            int x,y;
            cin>>x>>y;
            x--;
            x += N - 1;
            wrk.MAX[x].first = y;
            wrk.chg( (x - 1) / 2);
            //wrk.sh();
        }
	}

}
/*
5
2 4 1 3 5
3
s 2 4
u 1 10
s 1 3
*/