Kth Smallest Under Load

A leaderboard supports three operations, interleaved online, $2 \cdot 10^5$ of them in total, with scores that are integers in $[1, 10^9]$ :

insert(v)
erase(v)
kth(k) returning the $k$ -th smallest score currently present

Which structure serves all three, and what exactly is missing from the near misses?

A sorted std::vector with lower_bound to find the position, so kth(k) is an $O(1)$ index and inserts stay logarithmic.

A Fenwick tree of counts indexed by compressed score, giving insert and erase in $O(\log n)$ and kth by descending the tree in $O(\log n)$ . Total about $2 \cdot 10^5 \cdot 18 \approx 3.6 \cdot 10^6$ steps.

A min-heap. insert and erase are $O(\log n)$ and kth(k) is the $k$ -th pop, so all three are logarithmic.

A plain balanced binary search tree keyed by score, with no augmentation. It keeps everything in sorted order and therefore answers all three in $O(\log n)$ .