➤ Problem Link : GSS5
👉 Hint : Segment Tree with prefix, suffix, maximum and total sum in node
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mp make_pair
struct Node{
ll tsum,pfx,sfx,mx;
};
Node st[400001];
ll arr[100001];
typedef struct Node NODE;
void build(int v, int l, int r)
{
if(l==r)
{
st[v].tsum=st[v].pfx=st[v].sfx=st[v].mx=arr[l];
return;
}
int mid=(l+r)/2;
build(2*v,l,mid);
build(2*v+1,mid+1,r);
st[v].tsum=st[2*v].tsum+st[2*v+1].tsum;
st[v].pfx=max(st[2*v].pfx,st[2*v].tsum+st[2*v+1].pfx);
st[v].sfx=max(st[2*v+1].sfx,st[2*v+1].tsum+st[2*v].sfx);
st[v].mx=max(st[2*v].sfx+st[2*v+1].pfx,max(st[2*v].mx,st[2*v+1].mx));
}
Node query(int v,int s, int e, int l, int r)
{
Node q;
q.tsum=0;
q.pfx=q.sfx=INT_MIN;
q.mx=INT_MIN;
if(s>r || e<l)
{
return q;
}
if(s>=l && e<=r)
return st[v];
int mid=(s+e)/2;
Node lt=query(2*v,s,mid,l,r);
Node rt=query(2*v+1,mid+1,e,l,r);
q.tsum=lt.tsum+rt.tsum;
q.pfx=max(lt.pfx,lt.tsum+rt.pfx);
q.sfx=max(rt.sfx,rt.tsum+lt.sfx);
q.mx=max(lt.sfx+rt.pfx,max(lt.mx,rt.mx));
return q;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m,x1,y1,x2,y2;
cin>>n;
for(int i=1;i<=n;i++)
cin>>arr[i];
build(1,1,n);
cin>>m;
while(m--)
{
cin>>x1>>y1>>x2>>y2;
if(x2==y1)
cout<<query(1,1,n,x1,y1).sfx+query(1,1,n,x2,y2).pfx-arr[x2]<<"\n";
else if(x2==y1+1)
cout<<query(1,1,n,x1,y1).sfx+query(1,1,n,x2,y2).pfx<<"\n";
else if(x2>y1)
cout<<query(1,1,n,x1,y1).sfx+query(1,1,n,x2,y2).pfx+query(1,1,n,y1+1,x2-1).tsum<<"\n";
else
cout<<max(query(1,1,n,x1,x2).sfx+query(1,1,n,x2,y2).pfx-arr[x2],max(query(1,1,n,x2,y1).mx,query(1,1,n,x2,y1).sfx+query(1,1,n,y1,y2).pfx - arr[y1] ))<<"\n";
}
}
}
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.