Order Statistics Live — Solution & Editorial

Back to the Problem

Coordinate-compress all inserted values (read the operations offline), then a Fenwick tree of counts supports insert/delete in O(log) and k-th smallest by binary search (or Fenwick descent).

Complexity: O(Q log Q)

Watch out: Deleting a value not present must be a no-op; and compression must cover values that are inserted.