➤ Problem Link : HORRIBLE
👉 Hint : Segment Tree with Lazy Propagation
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll st[4*100001];
ll lazy[4*100001];
void propagateLazy(int ind,int l,int r)
{
if(l!=r)
{
lazy[2*ind+1]+=lazy[ind];
lazy[2*ind+2]+=lazy[ind];
}
st[ind]+=lazy[ind]*(r-l+1);
lazy[ind]=0;
}
void update(int ind,int l,int r,int ql,int qr,int v)
{
if(lazy[ind])
propagateLazy(ind,l,r);
if(l>qr || r<ql)
return;
if(ql<=l && r<=qr)
{
lazy[ind]+=v;
propagateLazy(ind,l,r);
return;
}
int m=(l+r)/2;
update(2*ind+1,l,m,ql,qr,v);
update(2*ind+2,m+1,r,ql,qr,v);
st[ind]=st[2*ind+1]+st[2*ind+2];
}
ll query(int ind,int l,int r,int ql,int qr)
{
if(lazy[ind])
propagateLazy(ind,l,r);
if(l>qr || r<ql)
return 0;
if(ql<=l && r<=qr)
return st[ind];
int m=(l+r)/2;
return query(2*ind+1,l,m,ql,qr)+query(2*ind+2,m+1,r,ql,qr);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n,c,p,q,v;
bool i;
cin>>n>>c;
memset(st,0,sizeof(st));
memset(lazy,0,sizeof(lazy));
while(c--)
{
cin>>i;
if(i)
{
cin>>p>>q;
cout<<query(1,1,n,p,q)<<endl;
}
else
{
cin>>p>>q>>v;
update(1,1,n,p,q,v);
}
}
}
}
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.