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
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
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.
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.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.
thx it worked !
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.