Sqrt decomosition, Trie
Given an array A of N integers, you have to process two types of query on the array:
- L R: find the minimal number in the subarray A[L…R] and count how many times it appears there.
- L R K: replace each number Ai with the expression (Ai xor K) for the subarray A[L…R].
Sqrt Decomposition and Trie building:
Split the numbers in sqrt(N) blocks, where each block contains sqrt(N) numbers. If you are not familiar with sqrt(N) decomposition you may read the section “O(N), sqrt(N) solution” of this tutorial which explains how to answer RMQ with sqrt(N) decomposition.
Let every number Ai = a1a2… a16 be a 16-bit binary number where a1 denotes the most significant bit and a16 denotes the least significant bit. The maximum value is less than 65536, so 16 bits are enough to represent the numbers, 216 = 65536.
Now for each block build a Trie, where all the numbers of that block are inserted into the Trie as a 16-bit binary number. That means, each edge of the trie is either 0 or 1 representing a bit of the numbers.
2nd type of query:
2 L R K
Let pending[j] = The pending value that has to be xor-ed with all the numbers on the j-th block.
Whenever the j-th block is completely inside an update of this type, the new value of pending[j] will be pending[j] xor K .
There could be at most two blocks (the blocks corresponding to left and right endpoint of the query) which are partially covered by the query. For each number Ai inside the query from such blocks just update the new value to be (Ai xor K ). Also delete the old value from the trie of that blocks and insert the new value to the trie.
As there would be at most sqrt(N) blocks and at most 2 * sqrt(N) indexes total on the partially covered blocks and inserting and deleting into the trie takes 16 nodes: the complexity of each type 2 updates would be O(sqrt(N)*16).
1st type of query:
1 L R
Take the minimum of the numbers from each blocks which is completely covered by the query range. All the numbers of j-th block (a block covered completely) has to be xor-ed with pending[j]. For finding the minimum value Ai xor pending[j] (Ai is a number in the trie of that block), the strategy is to try finding each bit of Ai from first bit to last bit. With each k-th bit, check whether the k-th bit can be same as the k-th bit of pending[j], if not then make it different.
After each step, we know one more bit of Ai and that is why Trie can help us in this process. We just need to store the current node of the Trie which corresponds to the current prefix of Ai. From this node we can easily check whether the next bit of Ai can be 0 or 1 and make the decision from that. To get the count of the minimum just store the additional info about the count of how many times a node is visited.