Movatterモバイル変換

I think this can be dine in O(1) per query by keeping track of number of numbers that turn bit k on for all 30-something bits. If there number of numbers with bit k > 0, then the bitwise or must turn bit k on as well.

Thus creating a 30*n = O(n) solution.

Its not easy to make constant factor of $$$O(1)$$$ solution (if it exists) significantly faster than $$$O(\log V)$$$

This is kinda similar to what I wondered about recently:https://codeforces.com/blog/entry/138297

No one knew how to do that :(

This is not a solution, but is something I thought about and made me not conclude that this task is immediately impossible.

Consider replacing each element with a random submask (each bit taken away with 1/2, easily done in O(1), assuming you can generate a random number in O(1)), and replace the OR with a XOR. This now gives an O(n) solution where every '1' bit is defintiely a '1', and every '0' have 1/2 chance to be actually a '1'.

If you repeat the above enough times, then you can gurantee the answers are correct with high probability. Unfortunately, you need to repeat it $$$c \log n \log \log n$$$ times here.

But if you are for some reason working with $$$a_i$$$ lower than the allowed range of bitwise operations to be O(1), say if $$$a_i\leq 32$$$, then you can simultaneously do the above operation using the same 64-bit integers packing multiple copies of $$$a_i$$$. This means that the $$$n log n log log n$$$ can improved if not all bits are not utilised.

Again, this is not a solution and may not be useful, but it could be interesting.