Implement order statistics tree using binary trie —
maintain a
multiset $M$ which supports the following operations (all numbers
are between $0$ and $X$):
- $\texttt{insert}(x)$: insert $x$ in the multiset.
- $\texttt{remove}(x)$: remove one occurrence of $x$ from
$M$.
- $\texttt{less}(x)$: count how many numbers from $M$ are
less than $x$.
- $\texttt{kth}(k)$: find the $k$-th smallest integer in $M$
in $O(\log X)$.
Binary tries provide neat implementation of implicit/sparse
segment tree.