You are given an array A of N integers.

Create another array B containing all or-subarrays of A . i.e B contains $$$A_{l}|A_{l+1}|...A_{r}$$$ for all $$$1 <= l <= r <= N$$$

You are provided Q queries . n each query you have to print K-th smallest element of B.

$$$1 <= A_{i} <= 10^{5}$$$ $$$1 <= Q , N <= 10^{5}$$$ $$$1 <= k <= N*(N+1)/2$$$

Example

N = 3 A = [1, 2, 3] Q = 3 Queries = [1, 2, 6]

B = {1, (1|2), (1|2|3), 2, (2|3), 3} = {1, 3, 3, 2, 3, 3}

The queries are answered below

• The 1st smallest element is 1

• The 2nd smallest element is 2

• The 6th smallest element is 3.

Source?

https://discuss.codechef.com/t/another-or-related-problem/89877

Upd misunderstood the problem

not from distinct , k-smallest from all subarrays

Sorry my bad!

Aman_j1 Can you explain your solution of the particular problem you had mentioned in your original comment?

UPD: Nvm, I solved it.

Maybe solving this problem first will help: Link

Hi, I solved the problem which you linked, but I am still unable to solve this problem. Can you provide some hints? If this problem was to find the Kth distinct smaller OR, it would be easy. [ because the no of distinct OR's starting from some index would be (Max(A)) ]

Calculate pairs (value, count). There are at most O(N log A_max) of them.

does this seem right?

We can use persistent segment tree for this problem.

For each array element ending at jth index compute suffixes of all bitwise or values ending at jth index. For example take array = [3,1,4,2,6]

If we take j = 5 (1 based indexing) arr[5]=6 compute all bitwise or [7,7,6,6,6]

So in the range (1,2) make range update with value 7.

In the range (3,5) make range update with value 6.

We can now answer queries like kth min|max in a range.

Since, there could only $$$O(\log_2{}100000)$$$ range updates for a single index.

Preprocessing can be done in $$$O(n\log{}n\log{}\max{(ai)})$$$.

Queries can be performed in $$$O(q\log{}n)$$$.

For each endpoint of a subarray $$$i$$$, there are only $$$\log{A_i}$$$ possible subarray OR-sum values, so we can just find all of those values and the number of times each one occurs, sort them, then build a prefix sum array on the counts and binary search for when we reach a count of $$$k$$$ in each query.

edit: nvm someone already described this idea

Yes, you are correct. I had AC with this approach.

The only observation is that there won't be much distinct elements in the resultant OR array B. So we can create frequency map and then use Binary search on that.