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 l1 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 l1. Isn't it the number of elements in array divisible by 2 occurring before l1 (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? asked 21 Aug '15, 16:02

The question has been closed for the following reason "The question is answered, right answer was accepted" by dragonemperor 22 Aug '15, 09:09
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.
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. answered 22 Aug '15, 04:56
Thank you bro. I tried your method (before seeing your solution :) ) and got AC with 100 points. Then I saw your approach and learned how to do it in C++. Thank you for your help
(22 Aug '15, 09:08)
