Problem link:Difficulty :Medium Prerequisites :Binary Indexed Tree or Sets in C++[Balanced Binary Search Trees] Problem:You are given an array of N integers. You have to make M queries. Each query has one of the two types:
Also p is in [ 2 3 5] ExplanationLet us assume that we have a data structure which can give us the next number divisible by p in the range [l r] in O(t) time, t is what we will find out later. Can you give an estimate of total amortised cost on the total time complexity using the above data structure ? If we forget that there is any query of type 2, then what will be the total amortised cost ? As each number is less than 10^{9}, in the worst case a number can be divided by p by at most 30 times (when p is 2 and number is 10^{9}). So total time complexity would be O(t) * 30 * N Now Let us add queries of type 2. Each number which is replaced will require at most 30 steps to reach 1. So at most M numbers are added. So total time complexity is O(t) * 30 * (M + N) + Time required to change the data structure for query 2. Now, if t = O(log N), then we are done. The Data StructureWe will make 3 balanced binary search trees [ one for p = 2, other for p=3 and the last one for p=5 ]. Balanced Binary search trees to keep numbers in the sorted is implemented in C++ as "set" and in Java as HashSet or TreeSet. In our set , we will keep index of the numbers which are divisible by p. Let us solve for p = 2, rest primes are analogous to this case. Query of First Type : l r p Query of Second Type : l d Pseudo Code Other Data StructureWe can use Binary Indexed trees to solve this problem. We will make 3 binary indexed trees[p=2 ,3 and 5] of size N . We will keep 1 at index i if number in that index is divisible by p. Updating in Binary Indexed Tree Reporting in Binary Indexed Tree Thus Overall time complexity of querying from both the structure is O(log N) Subtasksubtask 1: Subtask 2: Maintain 3 arrays for the counter and as soon as a Divide query comes for prime p, you can simply do Add 1 at position l and 1 to Position r+1 in array made for prime p. This will give you the power of p which is proposed to be divided for each index. Some Important Links to ReadSets in Cplusplus
Binary Indexed Tree in Topcoder Setter and Tester Solutions:
This question is marked "community wiki".
asked 28 Sep '14, 14:01

Segment Trees with lazy update were also possible for 100p. ( http://www.codechef.com/viewsolution/4919355 ) answered 28 Sep '14, 14:07
2
i just used segment tree without lazy updates and it passed. not that data is weak or something, but there is a 100 point soln without lazy prop too
(28 Sep '14, 14:09)
I just thought that this solution was also worth mentioning.
(28 Sep '14, 14:12)
1
@alexvaleanu, can you please explain what to store in a node? I am not clear how can we perform the operation of dividing only the the elements which are divisible by p.
(28 Sep '14, 14:25)
Check my solution : http://www.codechef.com/viewsolution/4919355
(28 Sep '14, 14:31)

This problem can also be done by sqrt decomposition. answered 28 Sep '14, 14:50

Well I also used segment tree but I wouldn't call it lazy propagation.I just stored the count of each primes i.e no of times all the numbers are to be divided by a particular prime,if they are divisible. My solution : http://www.codechef.com/viewsolution/4916671 answered 28 Sep '14, 14:48

I used almost the same approach but got WA throughout the contest. I found the bug in the last few minutes which was that "a single number can be present in more than one set". In the pseudo code above, the author is taking care of this situation while reading the input, and in update query, but I cannot see it in "report query". And while posting my doubt here, I was trying to give examples of such number (ex 30, 10) but then I realized that we don't need this check there! :D Hence, I got the answer while posting the question itself... :) answered 28 Sep '14, 14:52

I have followed the same algorithm as described above. I have used set in c++. But I am getting WA. Kindly advise me where i am going wrong? Thank you. Code Link : http://ideone.com/NIa8Ai answered 02 Oct '14, 15:48

answered 07 Oct '14, 10:32

@neo1tech9_7 can u please explain me your sqrt root decomposition solution ? answered 16 Jul '15, 08:09

only a lazy tree serves the purpose .. :) answered 17 Aug '17, 22:58
