### ram2012k's blog

By ram2012k, 3 years ago,

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 1st smallest element is 1

• The 2nd smallest element is 2

• The 6th smallest element is 3.

• 0

| Write comment?
 » 3 years ago, # |   +1 Source?
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # | ← Rev. 7 →   0 Upd misunderstood the problem
•  » » 3 years ago, # ^ |   0 not from distinct , k-smallest from all subarrays
•  » » » 3 years ago, # ^ |   0 Sorry my bad!
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Aman_j1 Can you explain your solution of the particular problem you had mentioned in your original comment?UPD: Nvm, I solved it.
 » 3 years ago, # |   +3 Maybe solving this problem first will help: Link
•  » » 3 years ago, # ^ |   0 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)) ]
•  » » » 3 years ago, # ^ |   0 Calculate pairs (value, count). There are at most O(N log A_max) of them.
•  » » » » 3 years ago, # ^ |   0 does this seem right? set of pairs S[n] element,count for elements in array(n to 1) { if(index is n) S[index].insert(array[index],1) else { S[index].insert(array[index],1) for j in S[index+1] if(j.first|array[index] exists in S[index]) { //find the pair, and increment count by 1 and insert back into the set } else S[index].insert(j.first | array[index],j.second) } } 
 » 3 years ago, # |   0 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)$.
 » 3 years ago, # | ← Rev. 2 →   0 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
•  » » 3 years ago, # ^ |   0 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.