### SupaHotFire's blog

By SupaHotFire, history, 10 days 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

•  » » 10 days 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 days 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 days 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.