Author: Anton Trygub
Solved by:
First to solve: RAF Penguins
Firstly, let's understand how to solve the problem for a single query.
Let's sort the array for which we are solving the problem, let its elements be [b_1, b_2, \ldots, b_k]. Suppose that it's possible to split its elements into groups and so that OR of the numbers from = AND of the numbers from = . Then, all numbers less than have to go to , and all numbers larger than have to go to . So, some prefix of the sorted array will go to the first group, and the remaining suffix — to the second. We can check if there exists such splitting point with counting all prefix OR and suffix AND.
This already gives an O(qn\log(n)) solution, but this is too slow, of course. How to do better than this?
Let's dive a bit deeper. Again, suppose that it's possible to split its elements into groups and so that OR of the numbers from = AND of the numbers from = . Suppose that has bits on. Then, all numbers with less than bits on have to get into , and all numbers with more than bits on have to get into . What about the numbers with exactly bits?
There are cases: all of them go to the same group, or some go to and some to , let's consider the second case. Suppose that number with bits goes to and number with bits goes to . Note that AND a = a, as AND x = x and OR a = x. So, we must have a=b. But then, all numbers with bits have to be equal.
Now, let's keep some data structure allowing us to find AND and OR of elements with exactly bits on a segment for every from to : segment tree works, sqrt decomposition also works. To process the query, find AND and OR of elements with exactly bits on this segment for every , and precompute prefix ANDs and suffix ORs. Note that the only case where we don't simply put all numbers with bits to and with bits to is when the prefix OR of all numbers with bits = suffix AND of all numbers with bits, and all numbers with exactly bits are the same, and there are at least of them, which is easy to check now.
Complexities for this solution can vary from O((n + q \log n) \cdot b) (with segment tree) to O(n \sqrt{n} + (q + n) \cdot b) (Mo's algorithm) or even O(n \log n + (q + n) \cdot b) (with divide & conquer), where b=30 is the number of bits.