Ande ka Funda - EDITORIAL:
Author: sachin_yadav
Editorialist: sachin_yadav
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Segment Trees, Lazy Propagation
PROBLEM:
Given an array N integers and Q queries. Each query can be of two types, t=1: given L and R, find count of numbers between L and R (both inclusive) divisible by 3. In query of type t=2, the numbers in range L to R are increased by a given number x.
EXPLANATION:
We build a segment tree over the array. The node of segment tree contains the information of how many integers in its range have 0, 1 and 2 (mod 3). We use lazy tree for fast updates of values.
When updating a segment tree node by x, make x = x\%3. Now the 0\: mod \:3 count will become count of x\%3 of that node, mod \:1 count will become count of (x+1)\%3 and 2\:mod\:3 count will become count of (x+2)\%3 of that node.
Complexity : O(\;N*log(Q)\;)
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
// #define tree_size 100
// #define arr_size 100
#define arr_size 100001
#define tree_size 262145
unsigned int seg_tree[tree_size][3], lazy_tree[tree_size], T, N, arr[arr_size] , Q;
unsigned int L, R, x, q_type;
void build_tree(int s, int e, int tree_idx)
{
if(s>e) return ;
if(s==e){ seg_tree[tree_idx][arr[s]%3]++; return; }
int mid=(s+e)/2;
build_tree(s, mid, tree_idx*2); build_tree(mid+1, e, tree_idx*2+1);
for(int i=0; i<3; ++i)
seg_tree[tree_idx][i]=seg_tree[tree_idx*2][i] + seg_tree[tree_idx*2+1][i];
}
void update_lazy(int l, int r, int s, int e, int tree_idx, int change)
{
if(s>e) return;
lazy_tree[tree_idx]%=3;
if(lazy_tree[tree_idx])
{
int x=lazy_tree[tree_idx];
lazy_tree[tree_idx]=0;
int temp[3]; for(int i=0; i<3; ++i) temp[i]=seg_tree[tree_idx][i];
for(int i=0; i<3; ++i) seg_tree[tree_idx][(i+x)%3] = temp[i];
if(s!=e){
lazy_tree[tree_idx*2]+=x;
lazy_tree[tree_idx*2+1]+=x;
}
}
if(r<s || e<l) return ;
if(s>=l && e<=r){
int temp[3]; for(int i=0; i<3; ++i) temp[i]=seg_tree[tree_idx][i];
for(int i=0; i<3; ++i) seg_tree[tree_idx][(i+change)%3] = temp[i];
if(s!=e){
lazy_tree[tree_idx*2]+=change;
lazy_tree[tree_idx*2+1]+=change;
}
return ; }
int mid=(s+e)/2;
update_lazy(l, r, s, mid, tree_idx*2, change);
update_lazy(l,r, mid+1, e, tree_idx*2+1, change);
for(int i=0; i<3; ++i)
seg_tree[tree_idx][i]=seg_tree[tree_idx*2][i] + seg_tree[tree_idx*2+1][i]; for(int i=0; i<3; ++i)
seg_tree[tree_idx][i]=seg_tree[tree_idx*2][i] + seg_tree[tree_idx*2+1][i];
}
int query_div_3(int l, int r, int s, int e, int tree_idx)
{
if(s>e) return 0;
lazy_tree[tree_idx]%=3;
if(lazy_tree[tree_idx])
{
int change=lazy_tree[tree_idx];
lazy_tree[tree_idx]=0;
int temp[3]; for(int i=0; i<3; ++i) temp[i]=seg_tree[tree_idx][i];
for(int i=0; i<3; ++i) seg_tree[tree_idx][(i+change)%3] = temp[i];
if(s!=e){
lazy_tree[tree_idx*2]+=change;
lazy_tree[tree_idx*2+1]+=change;
}
}
if(r<s || e<l) return 0;
if(s>=l && e<=r) return seg_tree[tree_idx][0];
int mid=(s+e)/2;
return query_div_3(l, r, s, mid, tree_idx*2) + query_div_3(l,r, mid+1, e, tree_idx*2+1);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>T;
while(T--)
{
memset(seg_tree, 0, sizeof(seg_tree)); memset(lazy_tree, 0, sizeof(lazy_tree)); memset(arr, 0, sizeof(arr));
cin>>N;
for(int i=0; i<N; ++i) cin>>arr[i];
build_tree(0, N-1, 1);
cin>>Q;
while(Q--)
{
cin>>q_type>>L>>R;
L--; R--;
if(q_type==1)
cout<<query_div_3(L, R, 0, N-1, 1)<<"\n";
else{
cin>>x;
update_lazy(L, R, 0, N-1, 1, x%3);
}
}
}
return 0;
}