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();
}