Author - Sweta Seth
Tester - Sweta Seth
Editorialist - Sweta Seth
Difficulty - Easy-Medium
Problem:
In the problem, it is required first update the Kth index with given value U and then find the minimum power from range [A,B]
Explanation:
Solution:
C++:
Setter’s Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll range = (1<<20)*4;
vector<ll> seg(range);
vector<ll> v(range);
void build(ll idx, ll low, ll high){
if(low == high){
seg[idx] = v[low];
return;
}
ll mid = (low+high)/2;
build((2*idx+1),low,mid);
build((2*idx+2),mid+1,high);
seg[idx] = max(seg[2*idx+1],seg[2*idx+2]);
}
void updateVal(ll ind, ll val, ll low, ll high, ll idx){
if(low == high){
seg[idx] = val;
return;
}
ll mid = (low+high)/2;
if(ind >= low && ind <= mid)
updateVal(ind,val,low,mid,(2*idx+1));
else
updateVal(ind,val,mid+1,high,(2*idx+2));
seg[idx] = max(seg[2*idx+1],seg[2*idx+2]);
}
ll findRangeMax(ll l, ll r, ll low, ll high, ll idx){
if(low >= l && high <= r)
return seg[idx];
if(high < l || low > r)
return LONG_MIN;
ll mid = (low+high)/2;
ll left = findRangeMax(l,r,low,mid,(2*idx+1));
ll right = findRangeMax(l,r,mid+1,high,(2*idx+2));
return max(left,right);
}
int main(){
ll n,t,k,u,a,b;
cin>>n>>t;
for(ll i = 0; i < n ; i++)
cin>>v[i];
build(0,0,n-1);
for(ll i = 0; i < t; i++){
cin>>k>>u>>a>>b;
updateVal(k-1,u,0,n-1,0);
cout<<(findRangeMax(a-1,b-1,0,n-1,0))<<'\n';
}
return 0;
}