If the problem only had queries of type 2 and type 3, then it could be easily solved by using a segment tree and lazy propagation. From here, it is assumed that the reader is familiar with this data structure.

A simple observation

One simple remark we can make is that for queries of type 1, we only need to update the value of element \(a_i\) at most \(\lfloor log_2(a_i) \rfloor + 1\) times (assuming there are no other queries of type 2 that modify the value of \(a_i\)), simply because the value we’re dividing by is at least \(2\). This simple observation is the key to this problem.

A simple optimization

Normally, if we could use lazy propagation for queries of type 3, then we can mark a node \(i\) once it’s completely contained within the segment \([L, R]\) and stop here. Unfortunately, not all the numbers in the segment corresponding to node \(i\) may be the same, so we are forced to go further down the tree. However, we can still choose which nodes we visit.

If all the elements in the segment corresponding to a child node \(j\) are equal to \(0\), then obviously there’s no point in going down this node, because none of the elements will be updated. Therefore, we will only go down nodes that contain non-zero elements. Once we visit a node that only contains elements that have the same value \(a_i\), we can mark this node with the new value \(\lfloor \frac{a_i}{x} \rfloor\) and stop.

This optimization may seem minor, but in fact, the time complexity of this algorithm is \(O(\log N \log \max(x)))\). An analysis of the time complexity is given below.

Time complexity analysis

Define the function \(F(i)\) as follows:

• If the segment corresponding to node \(i\) in the segment tree consists of the same positive number \(x\), and no other parent node of node \(i\) has this property, then \(F(i) = \lfloor \log(x) \rfloor + 1\).
• Otherwise, \(F(i) = 0\).

Let \(S\) be the current sum of all \(F(i)\) at some point during the processing of queries. Now we will consider how the value of \(S\) changes over time.

For queries of type 2, some nodes which correspond to sections of the segment \([L, R]\) will be marked with a new value \(x\). The number of nodes we mark is around \(O(\log N)\), and the value of \(F\) for these nodes increases by at most \(O(\log \max(x))\). Therefore, the value of \(S\) increases by at most \(O(\log N \log \max(x)))\).

For queries of type 3, we never go down a node which only consists of zeroes, so we never go down a subtree which only consists of nodes whose value \(F(i)\) equals \(0\). Thus, each time we mark a node \(i\), we know that the value of \(F(i)\) is positive, and will decrease by \(1\) after we mark it.

After \(Q\) queries, the value of \(S\) is at most \(O(Q \log N \log \max(x)))\), so the number of times we mark a node (or decrease \(S\)) is also at most \(O(Q \log N \log \max(x)))\). This is the final time complexity of this algorithm.

Sample Code (C++)