➤ Problem Link : KGSS
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
pair<ll,ll> st[400001];
ll arr[100001];
void build(int v, int s, int e)
{
if(s==e)
{
st[v]=make_pair(arr[s],-1);
return ;
}
int mid=(s+e)/2;
build(2*v,s,mid);
build(2*v+1,mid+1,e);
vector<ll> vec;
vec.push_back(st[2*v].first);
vec.push_back(st[2*v+1].first);
vec.push_back(st[2*v].second);
vec.push_back(st[2*v+1].second);
sort(vec.begin(),vec.end(),greater<ll>());
st[v]=make_pair(vec[0],vec[1]);
}
void update(int v,int l, int r,int ind, int value)
{
if(l==r)
{
st[v].first=value;
return;
}
int mid=(l+r)/2;
if(ind>=l && ind<=mid)
update(2*v,l,mid,ind,value);
else
update(2*v+1,mid+1,r,ind,value);
vector<ll> vec;
vec.push_back(st[2*v].first);
vec.push_back(st[2*v+1].first);
vec.push_back(st[2*v].second);
vec.push_back(st[2*v+1].second);
sort(vec.begin(),vec.end(),greater<ll>());
st[v]=make_pair(vec[0],vec[1]);
}
pair<ll,ll> query(int v, int s, int e, int l, int r)
{
if(s>r || e<l)
return make_pair(-1,-1);
if(s>=l && e<=r)
return st[v];
int mid=(s+e)/2;
pair<int,int> p,q;
p=query(2*v,s,mid,l,r);
q=query(2*v+1,mid+1,e,l,r);
"<<q.second<<endl;
vector<ll> vec;
vec.push_back(p.first);
vec.push_back(q.first);
vec.push_back(p.second);
vec.push_back(q.second);
sort(vec.begin(),vec.end(),greater<ll>());
return make_pair(vec[0],vec[1]);
}
int main()
{
int n,q,l,r;
char c;
cin>>n;
for(int i=1;i<=n;i++)
cin>>arr[i];
build(1,1,n);
cin>>q;
while(q--)
{
cin>>c>>l>>r;
if(c=='Q')
{
pair<ll,ll> p=query(1,1,n,l,r);
cout<<p.first+p.second<<"\n";
}
else
{
update(1,1,n,l,r);
}
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.