PROBLEM LINK:
Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh
DIFFICULTY:
MEDIUM
PREREQUISITES:
Segment Tree with Lazy Updates
PROBLEM:
We are given a array A of size N and an integer X. Now we need to perform Q queries on the array. Each query can be of two types:-
- 1 l r Y - Add Y to each element between indices l and r (inclusive).
- 2 l r - Report the number of elements between indices l and r (inclusive) which are exactly divisible by X.
EXPLANATION:
We can solve this problem by segment tree. Since 1 ≤ X ≤ 10 , each node of the segment can have a maximum of 10 values each. Each value Vi denotes the number of elements in the range of the node which leave a remainder i, 0 ≤ i < X when divided by X.
Let us denote V[i] as the values of each node of the tree, i.e from V[0] to V[9], which is the number of values in the range of the node which leave a remainder i when divided by X.
We need to keep a lazy array for the range updates as usual. Each node of the lazy array will contain the value which needs to be added to each node in the range of the node.
Let us consider X = 5. When we update the values, suppose for a particular node which falls completely in the range of l to r, the number of elements which are exactly divisible by 5 is 8 (the element at V[0]). Now we want to add 7 to each of the elements in the given range. So we can observe that (0 + 7)%5 = 2, i.e. the elements which were previously leaving a remainder 0 when divided by 5, will leave a remainder of 2 now after adding 7, i.e. new value of the element V[2] will be the old value of V[0] i.e. 8. Similarly the elements which had a remainder 1 when divided by 5, will now leave a remainder of (1 + 7)%5 = 3, i.e. they will leave a remainder of 3 now. So V[3] will now get the old value of V[1]. It will go on in a circular fashion for each value from 0 to X-1. First we can store the new values in a temporary array, then after calculating the new values of each index from 0 to X-1, we can copy them over again.
When we are querying the tree, we need the number of values in the given range which are exactly divisible by X. The value V[0] is the required value, i.e the number of nodes in the range of the particular node which leave a remainder 0 when divided by X. We can simple return the sum of all these values of the tree nodes.
See solution for clarity.
AUTHOR’S AND EDITORIALIST’S SOLUTIONS:
Author’s and editorialist’s solution can be found here.