Find count of integers x such that x or y = x

Revision en1, by f2lk6wf90d, 2017-10-17 15:04:21

Hello everyone, I thought of this problem after reading 875D - High Cry and I can't figure out a solution.
Let's call an integer y a subset of an integer x, if x | y == x.

You have to answer q queries of two types:

  • 1 x Add the integer x to the set S. (initially, the set S is empty)
  • 2 x Of all the integers currently in S, how many is x a subset of?

x ≤ 109, q ≤ 105.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English f2lk6wf90d 2017-10-17 15:06:29 14
en1 English f2lk6wf90d 2017-10-17 15:04:21 474 Initial revision (published)