PROBLEM LINK:
Author: Konstantin Sokol
Tester: Gerald Agapov
Editorialist: Tasnim Imran Sunny
DIFFICULTY:
Medium
PREREQUISITES:
Sqrt decomosition, Trie
PROBLEM:
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 A_{i} with the expression (A_{i} xor K) for the subarray A[L…R].
EXPLANATION:
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 A_{i} = a_{1}a_{2}… a_{16} be a 16bit binary number where a_{1} denotes the most significant bit and a_{16} denotes the least significant bit. The maximum value is less than 65536, so 16 bits are enough to represent the numbers, 2^{16} = 65536.

Now for each block build a Trie, where all the numbers of that block are inserted into the Trie as a 16bit 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 xored with all the numbers on the jth block.
Whenever the jth 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 A_{i} inside the query from such blocks just update the new value to be (A_{i} 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 jth block (a block covered completely) has to be xored with pending[j]. For finding the minimum value A_{i} xor pending[j] (A_{i} is a number in the trie of that block), the strategy is to try finding each bit of A_{i} from first bit to last bit. With each kth bit, check whether the kth bit can be same as the kth bit of pending[j], if not then make it different.
After each step, we know one more bit of A_{i} 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 A_{i}. From this node we can easily check whether the next bit of A_{i} 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.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.