# MULTQ3 - Editorial

MEDIUM

### EXPLANATION

The problem can be solved using segment trees. Every node of the tree stores the following data :

1. tree0[k] : In the range [low…high] covered by this node, how many numbers are divisible by 3 considering just additions performed on numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2
2. tree1[k] : In the range [low…high] covered by this node, how many numbers leave a remainder of 1 when divided by 3 considering just additions performed on numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2
3. add[k] : What is the quantity which is added to all numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2
5 Likes

Can we solve it using BIT? If yes then How??

6 Likes

#include

using namespace std;

int main()
{
int n,q;
scanf("%d %d", &n, &q);

``````    int a[3],coin[100001]={0},head;

while(q--)
{
for(int j=0;j<3;j++)
scanf("%d", &a[j]);

if(a[0] == 0)
{
for(int i=a[1];i<=a[2];i++)
coin[i]++;
}
else
{
for(int i=a[1];i<=a[2];i++)
if(coin[i]%3 == 0)

}
}
``````

}

WHY is this giving TLE error???

#include

using namespace std;

int main()
{
int n,q;
scanf("%d %d", &n, &q);

``````    int a[3],coin[100001]={0},head;

while(q--)
{
for(int j=0;j<3;j++)
scanf("%d", &a[j]);

if(a[0] == 0)
{
for(int i=a[1];i<=a[2];i++)
coin[i]++;
}
else
{
for(int i=a[1];i<=a[2];i++)
if(coin[i]%3 == 0)

}
}
``````

}

WHY is this giving TLE error???

You must use data structure in order to process any query in O(logn), not O(n), which let your solution TLE

plz elaborate your explaination…its too difficult too understand from such 3 confusing statements u have mentioned just for the sake of editorial… - _ -

Can anyone help me, pls ?? I use Segment Tree but I got Wrong Answer and I don’t know why. This is my submission, help me, please. https://www.codechef.com/viewsolution/13414560

Hey…I have solved this question using seg-trees but Im getting WRONG ANSWER. Here is my code.
https://www.codechef.com/viewsolution/15771326

How can one identify that this should be solved through segment tree ?
are there any ways to identify such problems (related to segment etc) ?
also is there any other way to solve this ?

@piyusjain1555 its a question of “lazy propagation” in “segment tree”… looks like you were a beginner for coding… so you can google and learn how to do this type of questions… u have have a look at FLIPCOIN which is similar to this question…

1 Like

The following is the idea.

Initially, all the numbers are divisible by 3. tree[node][0] = hi - lo + 1

Now, let’s say we are updating range [lo … hi] and hi - lo + 1 = 4.

Each update to range [lo … hi] of tree node moves the count in the following fashion.

Update number 1 -> all 0’s will be 1. 0000 -> 1111 and we save these numbers in tree[node][1]

Update 1: tree[node][1] = tree[node][0].

Update number 2 -> all 1’s will be 2. 1111 -> 2222. So we save these numbers in tree[node][2]

Update 2: tree[node][2] = tree[node][1].

Update number 3 -> all 2’s will be 3. 2222 -> 3333. They are now divisible by 3, so we save these numbers in tree[node][0]

Update 3: tree[node][0] = tree[node][2]

and so on.