mohmahkho's blog

By mohmahkho, history, 5 years ago, In English

Hi Codeforcers!
Recently I was trying to solve a query-type problem and after solving the problem I learned something new about C++ that I would like to share. Here's the problem statement:

We have a set that initially contains only a single 0. This set can contain multiple elements with the same value. We are given $$$Q$$$ queries. There are 3 types of queries:
1. INSERT x: Insert number x to the set,
2. DELETE x: Remove one occurrence of number x from the set. It is guaranteed that the number exists in the set,
3. MEDIAN: Print median of the numbers in the set. Median of a set of numbers is the middle element after sorting the numbers in the set in non-decreasing order. If the size of the set is a multiple of 2, among the two middle elements, print the left one.
Number of queries won't exceed $$$2 \cdot 10^5$$$.

I will assume that there is only INSERT/MEDIAN queries for convenience. DELETE operations are handled similar to INSERT in my solution.
Naive solutions won't pass the TL. By naive I mean inserting each element in $$$O(1)$$$ and for each MEDIAN queries sorting the container (probably std::vector) in $$$O(nlogn)$$$. This will lead us to an $$$O(Q\cdot n \cdot logn)$$$ total time complexity which won't pass the time limit with a strong test. I believe there is a solution using some non-STL data structures (e.g. policy based data structures, Fenwick Tree). However, we can solve this problem using std::multiset so we code less.

Solution
We take an iterator (std::multiset<T>::iterator) to the median and we maintain an index which is the 1-based index of the median element in the set.
If we got a MEDIAN query we will immediately print the median by dereferencing the iterator pointing to the median element. If we got an INSERT query we will insert the new element to the set and it is easy to see that by inserting one element the median index will change by at most one. So we can ++ or -- the iterator and keep maintaining the median element.

Implementation

At first I thought my solution is not going to work because inserting new element may invalidate iterators, but I was wrong. If you have an iterator pointing to an element of a set/multiset after inserting new elements into the set/multiset the mentioned iterator is still valid and you can use it. Similarly, if you delete an element which is not pointed by this iterator, this iterator is still valid and usable. that's why you can handle DELETE queries in this problem too (if you have understood this method so far that wouldn't be hard). Here are some references:
According to cppreference, std::multiset/insert: No iterators or references are invalidated.
Also, std::multiset/erase: References and iterators to the erased elements are invalidated. Other references and iterators are not affected.
I think it is good to mention that ++ and -- operators run in amortized constant time. (link)

I hope you've learned something new as I did :). Thank you.

  • Vote: I like it
  • +29
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Just for completeness, what do you do when you delete the median element?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    If the median is going to be deleted either it's left or right is the new median. Compute the index for the new median and change the iterator. either ++ or -- it and erase the previous iterator (because previous was the median that we wanted to delete).

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to "compute the index"?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        The index for the median in our set is considered to be $$$\lceil\frac{n}{2}\rceil$$$ where $$$n$$$ is the size of the set(1-based indexing). We already have an index for the median but after removing the median element the index for the median is now $$$\lceil\frac{n-1}{2}\rceil$$$. I'll call them new and old indices. if new == old we just have to ++ the iterator otherwise we -- the iterator. We keep a copy of old median iterator and erase it.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks, i had some doubts regarding multiset/set iterator invalidation during erase but they are cleared now .

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Really nice trick .

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Nice trick, also you can have two sets: one in ascending order for elements to the right of the median and second one in descending order for elements to the left of the median, and them you do the same. I solved that problem with this approach, but yours is better.