➤ Problem Link : SEGSQRSS
👉 Hint : Build two Segment Trees with Lazy Propagation
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll st[400001],lazyAdd[400001],lazySet[400001];
ll arr[200001];
ll st2[400001];
void build(ll v, ll l, ll r)
{
if(l==r)
{
st2[v]=arr[l];
st[v]=arr[l]*arr[l];
lazySet[v]=lazyAdd[v]=0;
return;
}
ll mid=(l+r)/2;
build(2*v,l,mid);
build(2*v+1,mid+1,r);
st2[v]=st2[2*v]+st2[2*v+1];
st[v]=st[2*v]+st[2*v+1];
lazySet[v]=lazyAdd[v]=0;
}
void propagateLazy(ll v, ll l, ll r)
{
if(l!=r)
{
if(lazySet[v]==0)
{
lazyAdd[2*v]+=lazyAdd[v];
lazyAdd[2*v+1]+=lazyAdd[v];
}
else if(lazyAdd[v]==0)
{
lazySet[2*v]=lazySet[v];
lazySet[2*v+1]=lazySet[v];
lazyAdd[2*v]=lazyAdd[2*v+1]=0;
}
else
{
lazySet[2*v]=lazySet[v];
lazySet[2*v+1]=lazySet[v];
lazyAdd[2*v]=lazyAdd[v];
lazyAdd[2*v+1]=lazyAdd[v];
}
if(lazySet[v]!=0)
{
st[v]=(r-l+1)*lazySet[v]*lazySet[v];
st2[v]=(r-l+1)*lazySet[v];
}
st[v]+=(r-l+1)*lazyAdd[v]*lazyAdd[v]+2*st2[v]*lazyAdd[v];
st2[v]+=(r-l+1)*lazyAdd[v];
lazyAdd[v]=0;
lazySet[v]=0;
}
}
void updateAdd(ll v,ll s, ll e,ll l, ll r, ll x)
{
if(lazyAdd[v]!=0 || lazySet[v]!=0)
propagateLazy(v,s,e);
if(s>r || e<l)
return;
if(s>=l && e<=r)
{
lazyAdd[v]+=x;
propagateLazy(v,s,e);
return;
}
ll mid=(s+e)/2;
updateAdd(2*v,s,mid,l,r,x);
updateAdd(2*v+1,mid+1,e,l,r,x);
st2[v]=st2[2*v]+st2[2*v+1];
st[v]=st[2*v]+st[2*v+1];
}
void updateSet(ll v,ll s, ll e,ll l, ll r, ll x)
{
if(lazyAdd[v]!=0 || lazySet[v]!=0)
propagateLazy(v,s,e);
if(s>r || e<l)
return;
if(s>=l && e<=r)
{
lazyAdd[v]=0;
lazySet[v]=x;
propagateLazy(v,s,e);
return;
}
ll mid=(s+e)/2;
updateSet(2*v,s,mid,l,r,x);
updateSet(2*v+1,mid+1,e,l,r,x);
st[v]=st[2*v]+st[2*v+1];
}
ll query(ll v, ll s, ll e,ll l, ll r)
{
if(lazyAdd[v]!=0 || lazySet[v]!=0)
propagateLazy(v,s,e);
if(s>r || e<l)
return 0;
if(s>=l && e<=r)
return st[v];
ll mid=(s+e)/2;
return query(2*v,s,mid,l,r)+query(2*v+1,mid+1,e,l,r);
}
int main()
{
int t;
cin>>t;
for(int k=1;k<=t;k++)
{
ll n,q;
cin>>n>>q;
for(ll i=1;i<=n;i++)
cin>>arr[i];
build(1,1,n);
int x,l,r,b;
cout<<"Case "<<k<<":\n";
while(q--)
{
cin>>b;
if(b==2)
{
cin>>l>>r;
cout<<query(1,1,n,l,r)<<"\n";
}
else if(b==1)
{
cin>>l>>r>>x;
updateAdd(1,1,n,l,r,x);
}
else
{
cin>>l>>r>>x;
updateSet(1,1,n,l,r,x);
}
}
}
}
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.