Need help understanding editorial

bit

#1

Problem link

Editorial

I need help with BIT version of the solution. I get it how update is done. But divide part is causing problem for me.

We will find the sum of the values stored till l-1 for Binary Indexed tree of p. We will find the index of the next value which is just greater than the sum found. We will divide that index of the array by p. We will update our sum to this new sum. We will continue to do this till our index just exceeds r.

Here are my doubts : (consider the BIT storing index divisible by 2)

  1. Finding sum upto l-1. Isn’t it the number of elements in array divisible by 2 occurring before l-1 (inclusive)? If so, what is the purpose of it?

  2. How is the next index greater than present sum found? If we search each and every elements won’t it be linear?

  3. Is the approach by tester and setter different than the one described in the editorial?

  4. At the end there is another approach that uses prefix sum to find number of times a given element will be divisible by p. Won’t this affect the updation query? I mean suppose at index i value in array is 50. Let’s say there are 3 division operations for this index. Then let the value changes to 16. If we compute the division at the end, (after finding the prefix sum), there are three divisions for 50, not 16. Dividing 16 by 2 three times will result in incorrect answer. How is this problem handled?


#2

I don’t understand it either, but I can tell you how I solved it using a BIT. Frankly I don’t even see if thats the solution proposed by the editorial.

With 3 BITs you keep track on how often you have to divide the number in the array by 2,3 and 5. The division doesn’t happen till after all queries.

How to handle the two types of queries:

  1. 1 l r p add 1 at position l in the corresponding BIT and add -1 at r+1 (if r\lt n)
  2. 2 l d update the array a at position l. For the BIT: The fresh number doesn’t need to be divided. So get the current value at position l and subtract it from position l. To get the correct values for higher positions add the value to position l+1 (if l\lt n).

After the queries the BITs contain exactly how often each number has to be divided. So divide until you reach this limit or the number is not divisible any more.

My code.


#3

Thank you bro. I tried your method (before seeing your solution :slight_smile: ) and got AC with 100 points. Then I saw your approach and learned how to do it in C++.

Thank you for your help

My code