Order-statistics multiset
Your task
Implement an order-statistics multiset that supports insert, remove, and find-kth-smallest, all in O(log U). Process operations: ["insert", x] adds one copy of x; ["remove", x] removes one copy of x (guaranteed present); ["kth", k] returns the k-th smallest value currently in the multiset (1-indexed; guaranteed valid). Return the list of answers for the kth operations in order. All values that ever appear are known up front (they appear in the op list), so coordinate-compress and use a Fenwick tree with binary-search-on-BIT for the kth query.
Examples
kth_smallest_stream(ops: list) -> list[int]Example 1
Input
kth_smallest_stream([["insert", 5], ["insert", 1], ["insert", 8], ["kth", 1], ["kth", 2], ["insert", 3], ["kth", 2]])Output
[1, 5, 3]