How to find the number of elements in std::set less than a given K?

Question

C++ / C#

While solving one problem, the following problem arose:
We have a lot of elements (we can add and remove)
For a given number, we need to find the number of elements that are less than K.
A possible way to do this:

int d = distance(s.begin(), s.lower_bound(k));
However, such a trip is not optimal, here it is written why.
In short, since set does not have a RandomAccessIterator , the asymptotics will be linear .

Consider the Fenwick tree idea:

We can do the operation of adding and finding the quantity in O(log n), but the removal operation is not realizable.

The last idea is a cartesian tree:

This is exactly what we need!
This structure allows you to perform these and not only operations in O(log n) - excellent asymptotics.
However, in the condition of the Olympiad, writing such a structure is a rather complicated and time-consuming task.

So the question itself is:
How to solve the given problem using only built-in data structures.

The use of libraries like boost is undesirable, because they are not at the Olympiad either :)

Answer 1

If you write in GNU C++, then there is such a cheat: opentrains.mipt.ru/zksh/files/zksh2015/lectures/mi... (see 1.3)

Answer 2

You can use MinHeap (fixed size k, or not fixed).

Answer 3

std::set is implemented via a binary tree, it is sorted. Through the binary search algorithm you can find - complexity O (log (n))