SupaHotFire's blog

Find kth element in a multiset
By SupaHotFire, history, 16 months ago, In English

I did solve this problem for a set with binary searching in a BIT but for multiset I don't know how to solve it for example if the multiset elements are 3 3 3 my solution will only see the last element because BIT is a prefix sum and BIT array would be BIT[3]=3 so binary searching with query is not giving a correct answer because I'm looking for a certain value not a range using binarysearch

any advice would be appreciated

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think we can easily use pdbs in this case. link

ordered_set can be converted to ordered_multiset by converting less to less_equal in its declaration

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    Having the comparator as less_equal will only work for insert queries. While erasing, it will give unexpected results. The correct way is to keep a ordered_set of pairs as {$$$val, id$$$}.

    See this discussion for more details.

    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can't do that. STL and pb_ds requires the comparator to be partial order. It will cause undefined behavior to violate the rule.

    We can make the set element pair<int, int> and put an unique ID in the second field. Then it's exactly a multiset of the first field.

    → Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

You can still solve it using BIT by changing what you binary search for. In the case of sets, you binary search for smallest index with prefix sum=k. For multiset binary for smallest index with prefix sum>=k.

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Binary searching the BIT works in $$$O(\log^2 n)$$$. If you're ready to go deeper, there is an $$$O(\log n)$$$ solution called "binary lifting" (basically stepping through the internal structure of the BIT), explained in this blog entry.

→ Reply