khatribiru's blog

Need Help Please
By khatribiru, history, 8 years ago, In English

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

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by khatribiru (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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).

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, But Please explain the Dp solution for L=1 and R=N.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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[0][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.

      → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

Vai, can you please share the source of the problem? The problem seems interesting :)

→ Reply