Order Statistics Live

Difficulty: 1900 6000 ms 128 MB

binary-search fenwick

Maintain a multiset under three operations: I x insert x, D x delete one copy of x (if present), and K k print the k-th smallest element (or −1 if fewer than k exist).

Input: the first line has Q; each of the next Q lines is an operation.

Output: one line per K query.

Constraints:

• 1 ≤ Q ≤ 10⁵
• |x| ≤ 10⁹

Sample Tests

5
I 5
I 2
I 8
K 2
K 3

5
8

2
I 1
K 1

1

Read the Editorial