Let's solve the problem for the whole sequence instead of a given range.

We can store each number in a trie according to its binary representation from the most significant bit to the least significant bit. Each trie node represents a prefix in binary form and stores the number of integers of that prefix. Let this number be cntcnt of the node. Each node can have at most two child nodes (left & right) where the left node represents the bit of 0 after the current prefix and the right node represents the bit of 1 after the current prefix. Now let's iterate from the most significant bit to the least significant bit of xx and calculate the maximum sum of aixa_i \oplus x.

We will start from the root node of the trie. If the current bit of xx is 11, then it's optimal to take the numbers where the current bit is 00. If the count of such numbers (cntcnt of the left node of the current node) is greater than or equal to kk, we can move to the left node and we have to take all the kk integers from that node. Otherwise, we can take all numbers of the left node and move to the right node and we have to take the remaining (kz)(k-z) integers from the right node where zz is the number of integers (cntcnt) of the left node. While taking all the numbers from the left node, we have to calculate their contribution to the sum of XOR. To do this, in each node, we can also store the number of integers among the subtree of the current node having 1 at the ii-th bit for each ii from 00 to 3030 (as the maximum value of the input is less than 2302^{30}).

If the current bit of xx is 00, we can process it similarly. In this case, we try to take as many numbers as possible from the right node and the remaining from the left node.

This way we can get the maximum sum of XOR. How can we get the count of subsequences? The count of subsequences depends on the last node we are picking the numbers from. If the count of integers to the last node is nn and we need to pick rr integers from that node, the count of subsequences is (nr)n\choose r as there are (nr)n \choose r ways to pick rr integers from nn.

To solve the problem for a given range, we have to use Persistent Trie instead of a simple trie. The complexity is O(n×log2mO(n\times \log ^2 {m}) for building the trie with necessary information and O(log2mO(\log^2{m}) for each query where mm is the maximum value. Overall complexity O((n+q)×log2mO((n+q)\times\log^2m).

Statistics

58% Solution Ratio
rfpermenEarliest, Apr '22
MrBrionixFastest, 0.4s
adnan_tokyLightest, 530 MB
mumith_fahim99Shortest, 2701B
Toph uses cookies. By continuing you agree to our Cookie Policy.