Another OR Related Problem

I recently appeared for a contest and many questions were asked. I could solve all but 1.

The question is suppose you are given an array A consisting of N elements
Then form a new Array B, such that it contains binary or of elements from Al | Al+1 | . . | Ar
for all 1 <= l <= r <= N

for example given Array is A = [1, 2, 4]
then B contains = [1, 2, 4, 1|2, 2|4, 1|2|4] = [1, 2, 4, 3, 6, 7]

Given a list of Q Queries each query denoted a number K , we have to find the K’th smallest number in B

Lets say the queries are [2, 5]
then answer would be a list = [2, 6] // 2nd and 5th smallest element respectively

Assume all arrays are 1 indexed

Constraints
1 <= N <= 105
1 <= Q <= 105
1 <= A[i] <= 109

Time Limit: 4.sec

can anyone tell me how one could approach this

PS: I tried this article here but was not able to make much progress on finding rank of a number in subarray or

UPD: I HAVE SOLVED THE PROBLEM.

Tagging users
@taran_1407 @cubefreak777 @ashutosh450 @l_returns @vijju123 @nishant403 @anshugarg12 @ssjgz @ayush_2407

“Tagging most frequent posters”

  • Next time, don’t.
    Edit: I was tagged in the previous revision of the post
1 Like

ok. Since you are here. Would you please answer the question

Since there are only 30 bits in the numbers, the OR won’t change more than 30 times if you start from a certain index. So array B will only have Nlog(maxA) elements.

There are multiple ways to efficiently find those elements, for example, segtree+descent or sparse table+binary search.

2 Likes

Yeah I removed you from tag. Didn’t knew it would be a bother. Anyway I would try what u said below and see if i could make it work. Thanks anyway

I did see your video on segment tree and descent but am still confused how to do this. would you please explain in a bit more detail

Send the solution @roushan_17

can you share the solution