Here is the problem statement

I tried solving the problem by finding the minimum and maximum number in each range and solving the equation for both numbers and returning the maximum value. However, I got TLE. Can anyone help?

Here is my code:

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

#define ll long long
#define ar array
#define all(v)	 ((v).begin()), ((v).end())
#define sz(x) x.size()

int n;
const int MAX_N=8e5+5;
ar<ll, 2> tree[MAX_N];
vector<ll> a;


ar<ll, 2> comb(ar<ll, 2> x, ar<ll, 2> y){
    ar<ll, 2> ans;
    if(a[x[0]]<a[y[0]]) ans[0]=x[0];
    else if(a[x[0]]>=a[y[0]])ans[0]=y[0];

    if(a[x[1]]>a[y[1]]) ans[1]=x[1];
    else if(a[x[1]]<=a[y[1]]) ans[1]=y[1];

    return ans;
}

void add(int p, int ss, int se, int i, int v){
    if(ss==se){
        tree[p]={v,v};
        return;
    }
    if(i<=(ss+se)/2) add(2*p,ss, (ss+se)/2,i,v);
    else add(2*p+1,(ss+se)/2+1,se,i,v);
    tree[p]=comb(tree[2*p],tree[2*p+1]);

}


ar<ll, 2> get(int p, int ss, int se, int qs, int qe){
    if(ss>=qs && se<=qe) return tree[p];
    if(ss>qe || se<qs) return {n,n+1};
    int mid=(ss+se)/2;
    return comb(get(2*p,ss,mid,qs,qe), get(2*p+1,mid+1,se,qs,qe));
}

ll calc(ll x, ll y){
    return a[x]+(y/a[x]);

}

void solve(){
    cin >> n;
    a.resize(n+2);
    for(int i=0;i<n;++i) cin >> a[i], add(1, 0, n-1, i, i);
    a[n]=INT_MAX, a[n+1]=INT_MIN;
    int q; cin >> q;
    while(q--){
        int type; cin >> type;
        if(type==1){
            int index, val; cin >> index >> val, --index;
            a[index]=val;
            add(1,0,n-1,index,index);
        }else{
            ll l, r, y; cin >> l >> r >> y, --l, --r;
            ar<ll, 2> cur=get(1,0,n-1,l,r);
            if(calc(cur[0],y)>calc(cur[1],y)) cout << cur[0]+1 << endl;
            else cout << cur[1]+1 << endl;
        }
    }
 }

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
}