➤ Problem Link : MULTQ3
👉 Hint : Segment Tree with Lazy Propagation
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int lazy[4*100005];
pair<int,int> st[4*100005]; //mod 0 && 1
void build(int ind,int l,int r)
{
if(l==r)
{
st[ind].first=1;
st[ind].second=0;
return;
}
int m=(l+r)/2;
build(2*ind+1,l,m);
build(2*ind+2,m+1,r);
st[ind].first=st[2*ind+1].first+st[2*ind+2].first;
st[ind].second=st[2*ind+1].second+st[2*ind+2].second;
}
void propagateLazy(int ind,int l,int r)
{
lazy[ind]%=3;
if(l!=r)
{
lazy[2*ind+1]+=lazy[ind];
lazy[2*ind+2]+=lazy[ind];
}
int mod2=r-l+1-(st[ind].first+st[ind].second);
if(lazy[ind]==1)
{
st[ind].second=st[ind].first;
st[ind].first=mod2;
}
else
{
st[ind].first=st[ind].second;
st[ind].second=mod2;
}
lazy[ind]=0;
}
void update(int ind,int l,int r,int ql,int qr)
{
if(lazy[ind]%3!=0)
propagateLazy(ind,l,r);
if(r<ql || l>qr)
return;
if(ql<=l && r<=qr)
{
lazy[ind]+=1;
propagateLazy(ind,l,r);
return;
}
int m=(l+r)/2;
update(2*ind+1,l,m,ql,qr);
update(2*ind+2,m+1,r,ql,qr);
st[ind].first=st[2*ind+1].first+st[2*ind+2].first;
st[ind].second=st[2*ind+1].second+st[2*ind+2].second;
}
int query(int ind,int l,int r,int ql,int qr)
{
if(lazy[ind]%3!=0)
propagateLazy(ind,l,r);
if(r<ql || l>qr)
return 0;
if(ql<=l && r<=qr)
return st[ind].first;
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);
memset(lazy,0,sizeof(lazy));
int n,q,i,ql,qr;
cin>>n>>q;
build(1,1,n);
while(q--)
{
cin>>i>>ql>>qr;
if(i==0)
{
update(1,1,n,ql+1,qr+1);
}
else
{
cout<<query(1,1,n,ql+1,qr+1)<<endl;
}
}
}
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.