PROBLEM LINK: CDVB2022/CHEFXORQ
Author: madra
DIFFICULTY
Easy-Medium
PREREQUISITES
Bitwise operations, Prefix Sums
EXPLANATION
checking for every query if each A[i] with L ≤ i ≤ R satisfies the condition is O[n^2], which is too slow. As is always the case with such problems, we need to observe some structure to make this faster.
The key idea here is to look at the highest set bit of a number, i.e, the highest integer k such that 2^k occurs in the binary representation of that number. For example, the highest set bit of 44 is 22 (since 4 = 100_24=1002), and the highest set bit of 2121 is 44 (since 21 = 10101_221=101012).
For convenience, I’ll denote the highest set bit of an integer y > 0y>0 as h(y)h(y). Note that h(y)h(y) is not defined when y = 0y=0, since there are no set bits, so we consider it separately.
Now let’s look at the given operation in terms of the highest set bit. There are a few cases to consider.
With our cases in hand, it’s easy to see that the problem reduces to the following:
- If X = 0X=0, count the number of integers in range that are not zero
- If X > 0X>0, count the number of integers A[*i]* in range such that h(X)!=h(Ai)
Doing this fast is a simple application of prefix sums, as follows:
For each 0≤b<31 and each N1≤i≤N, let P{b, i} denote the number of indices j such that 1≤j≤i, and h(Aj)=b. P{b, i} is easily computed from P{b, i-1} by knowing the value of h(Ai) (add 11 if h(Ai)=b, add 00 otherwise), so this entire array can be computed in O(31⋅N).
Notice that this is essentially 31 separate prefix sum arrays, one corresponding to each bit. Similarly, create a prefix sum array corresponding to the value 00, since it doesn’t come under any of these.
With these arrays in hand, the answer to a query (L,R,X) is simply R−L+1−(Pb,R−Pb,L−1), where b = h(X)b=h(X) (and of course, treating the X = 0X=0 case similarly).
Time Complexity:
O(Q+31⋅N) per test.
SOLUTIONS
CPP: solution
JAVA: solution
Python: solution