### khatribiru's blog

By khatribiru, history, 7 years ago, You are given an array of numbers( N ) (a[i]<= 10^6 && N<= 10^5 ) And 10^5 Queries. In each query You will be given.

X L R.

You have to find the how many numbers are there between L to R such that ( ( a[i] & X )== X ) . Thanks in Advance Comments (5)
 » Auto comment: topic has been updated by khatribiru (previous revision, new revision, compare).
 » Suppose L = 1 and R = N for all queries. We can precalculate all answers using standart DP approach in .Now we want to choose some number B and divide the array to parts of size B. For all prefixes of length kB (for integer k) we will use DP approach and store all the answers. Now we can answer one query in O(B) time (sqrt-decomposition like).Total complexity: . We will choose thus getting .Not sure if it is good enough but better than O(QN).
•  » » Sorry, But Please explain the Dp solution for L=1 and R=N.
•  » » » Suppose we have array A of length 2n. We want to calculate array B such that .We will calculate DP[k][mask] = ΣsubmaskA[submask] where the first k bits in submask is subset of those bits in mask and other m - k are equal to bits in mask. Then DP[mask] = A[mask] and DP[m][mask] = B[mask].Now how to calculate this DP:if k-th bit in mask is 0 then DP[k][mask] = DP[k - 1][mask]if k-th bit in mask is 1 then DP[k][mask] = DP[k - 1][mask] + DP[k - 1][mask - 2k]It is O(n2n) or if C = 2n.
 » 6 years ago, # | ← Rev. 3 →   Vai, can you please share the source of the problem? The problem seems interesting :)