Another OR Related Problem

help
,
1

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

2

“Tagging most frequent posters”

  • Next time, don’t.
    Edit: I was tagged in the previous revision of the post
2 Likes
3

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

4

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
5

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

6

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

8

Send the solution @roushan_17

9

can you share the solution