### SupaHotFire's blog

By SupaHotFire, history, 9 months ago, ,

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

• 0

 » 9 months ago, # |   0 I think we can easily use pdbs in this case. linkordered_set can be converted to ordered_multiset by converting less to less_equal in its declaration
•  » » 9 months ago, # ^ | ← Rev. 2 →   +4 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.
•  » » 9 months ago, # ^ |   0 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 and put an unique ID in the second field. Then it's exactly a multiset of the first field.
 » 9 months ago, # |   +3 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.
•  » » 9 months ago, # ^ |   +3 thx it worked !
 » 9 months ago, # | ← Rev. 2 →   +3 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.