Assume that we only have query 1 and 3, and \(L=1,R=N\) for query 1.

Obviously the whole \(A\) will have only one kind of numbers after \(O(\log V)\) times of query 1. (\(V\) means \(\max\{a_i,y\}\)).

The \(\Theta(Q \sqrt{N \log N})\) solution

Consider SQRT Decomposition. That is, set a constant \(T\) and partition this array into \(N \over T\) blocks each containing \(T\) elements of \(A\). Then we can divide \([L,R]\) into some blocks and at most two parts of blocks.

We define a block which only has one kind of numbers as “assigned” block. Then, for any intact assigned block, the three kinds of queries on it has the time complexity \(\Theta(1)\).

When a block isn’t assigned, it’s initially not assigned or broken by queries. So the appearance times of not assigned blocks is \(O({N \over T}+Q)\).

For a not assigned block, one time of query 2 or \(O(\log V)\) times of query 1 will make it a assigned block.

So, we can maintain the sum in all the blocks. For queries, we jump between blocks. Once dealing with query 1 or 2, we modify blocks which are not assigned by brute force. By choosing a proper \(T\), the total time complexity is \(\Theta(Q \sqrt{N \log N})\).