Can someone point out the mistake ?
I referred some other blogs like Solution with explanation but I was not able to understand why in build function when left == right, why they are only adding to count_0.
Eg:- If left = 4 and right = 4 , then I think we should add at count_1 as left % 3 = 1,but they updated only for count_0.
My logic:
Make segment tree and at every node store count of values in that range with remainder =0 , 1 and 2.
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define M 1e9+7
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FOR0(i,n) for(ll i = 0 ; i < n ;i++)
#define FOR1(i,n) for(ll i = 1; i<= n;i++)
#define FOR2(i,s,e) for(ll i = s ; i<e; i++)
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define endl '\n'
#define INF 1000000000
#define D(x) cout << #x " = " << (x) << endl
using namespace std;
const int maxN = 1e5+1;
int lazy[4*maxN];
vi st[4*maxN];
void init(){
memset(lazy,0,sizeof(lazy));
vi temp(3,0);
for(int i =0 ; i < 4*maxN ;i++ ) {
st[i].clear();
st[i] = temp;
}
}
void build(int si,int ss,int se){
//if(ss >qe && se <qs) return;
if(ss == se){
if(si%3 ==0) st[si][0]+=1;
else if(si%3 ==1) st[si][1]+=1;
else st[si][2]+=1;
return;
}
int mid = (ss+se)>>1;
build(si<<1,ss,mid);
build(si<<1|1,mid+1,se);
st[si][0] = st[si<<1][0]+st[si<<1|1][0];
st[si][1] = st[si<<1][1]+st[si<<1|1][1];
st[si][2] = st[si<<1][2]+st[si<<1|1][2];
}
void update(int si,int ss,int se,int qs,int qe){
if(lazy[si]!=0) {
int dx = lazy[si];
lazy[si]=0;
int f1 =st[si][0],s1 = st[si][1],t1= st[si][2];
int check = dx % 3;
if(check == 0){//all good
}
else if( check == 1) {
int temp1 = s1,temp2 =t1;
s1 = f1;
t1 = temp1;
f1 = temp2;
st[si][0]=f1,st[si][1]=s1,st[si][2]=t1;
}
else if(check == 2) {
int temp1 = s1,temp2 =t1;
t1 = f1;
s1 = temp2;
f1 = temp1;
st[si][0]=f1,st[si][1]=s1,st[si][2]=t1;
}
if(ss !=se)
lazy[si<<2]+=dx,lazy[si<<2|1]+=dx;
}
if(ss >qe && se <qs) return;//completely outside
if(ss >=qs && se <= qe){//completely inside
//update according to 1
int f1 =st[si][0],s1 = st[si][1],t1= st[si][2];
int temp1 = s1,temp2 =t1;
s1 = f1;
t1 = temp1;
f1 = temp2;
st[si][0]=f1,st[si][1]=s1,st[si][2]=t1;
if(ss !=se)
lazy[si<<2]+=1,lazy[si<<2|1]+=1;
return;
}
// overlap
int mid = (ss+se)>>1;
update(si<<1,ss,mid,qs,qe);
update(si<<1|1,mid+1,se,qs,qe);
st[si][0] = st[si<<1][0]+st[si<<1|1][0];
st[si][1] = st[si<<1][1]+st[si<<1|1][1];
st[si][2] = st[si<<1][2]+st[si<<1|1][2];
}
int query(int si,int ss,int se,int qs,int qe){
if(lazy[si]!=0) {
int dx = lazy[si];
lazy[si]=0;
int f1 =st[si][0],s1 = st[si][1],t1= st[si][2];
int check = dx % 3;
if(check == 0){//all good
}
else if( check == 1) {
int temp1 = s1,temp2 =t1;
s1 = f1;
t1 = temp1;
f1 = temp2;
st[si][0]=f1,st[si][1]=s1,st[si][2]=t1;
}
else if(check == 2) {
int temp1 = s1,temp2 =t1;
t1 = f1;
s1 = temp2;
f1 = temp1;
st[si][0]=f1,st[si][1]=s1,st[si][2]=t1;
}
if(ss!=se)
lazy[si<<2]+=dx,lazy[si<<2|1]+=dx;
}
if(ss >qe || se < qs) return 0;//completely outside
if(ss >=qs && se <= qe){//completely inside
return st[si][0];
}
// overlap
int mid =(ss+se)>>1;
return (query(si<<1,ss,mid,qs,qe)+ query(si<<1|1,mid+1,se,qs,qe));
}
int main(){
IOS
int n,q,a,b,c;
init();
cin>>n>>q;
build(1,1,n);
while(q--){
cin>>a>>b>>c;
++b;++c;
if( a == 0)
update(1,1,n,b,c);
else
cout<<query(1,1,n,b,c)<<endl;
}
}