Блог пользователя ram2012k

Find Kth smallest element from all or-subarrays
Автор ram2012k, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Source?

→ Ответить
»
3 года назад, # |
← Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

Upd misunderstood the problem

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Maybe solving this problem first will help: Link

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 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 года назад, # |
  Проголосовать: нравится 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 года назад, # |
← 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 года назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить