Order-statistics multiset
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.
kth_smallest_stream(ops: list) → list[int][[["insert",5],["insert",1],["insert",8],["kth",1],["kth",2],["insert",3],["kth",2]]]out[1,5,3]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[["insert",5],["insert",1],["insert",8],["kth",1],["kth",2],["insert",3],["kth",2]]][1,5,3]not run yetsample