Given an array A of N integers. You want to support Q queries over it of following three types.
- 1 L R X: multiply each number in the range A_L, A_{L + 1}, ..., A_R by X.
- 2 L R Y: Replace the elements A_L, A_{L + 1}, ..., A_R by Y, 2 * Y, ... (R - L + 1) * Y. In other words, the number A_i will be equal to (i - L + 1) * Y for each i from L to R.
- 3 L R: Find the number of trailing zeros in A_L \cdot A_{L + 1}. \dots . A_R.
We need to create a data structure which answer these over the array. We will use segment tree for it. Let us see what should we store in the segment tree node.
For supporting query of first type, we should be able to multiply all the elements in segment tree node by X. For this, you can associate an integer with the node representing the multiplicand that needs to be multiplied with the elements in the range to find their actual value.
For supporting queries of second type, you will replace the array indices represented by the node A_{lo}, A_{i + 1}, ..., A_{hi} by i \cdot Y, (i + 1) \cdot Y + .... Instead of actually replacing the elements, we will need to store some information in the segtree node so that we can do this operation faster. For that, we will need to maintain the value i and Y. Note that this operation will replace the values, so you should also reset the multiplicand for the node by 1.
Let us now support the last query. We need to find number of trailing zeros in the product of the numbers in the range of segment tree node. For that, we should know the number of times 2 and 5 divide the product of numbers. For this, we can store count of number of times 2 and 5, cnt_2, cnt_5 divide the product.
Time complexity of each operation is \mathcal{O}(log N). Building the segment tree will take \mathcal{O}(N) time. Hence overall time complexity will be \mathcal{O}(N) + \mathcal{O}(Q \, log N) = \mathcal{O}(Q \, log N)