2235. The kth Largest While the Set Changes

A collection of integers starts empty. Then q operations arrive, one per line:

add v put another copy of v into the collection del v take one copy of v out of the collection big k print the kth LARGEST stored key, or none

Copies count, so with 2, 2 and 5 stored the 1st largest is 5 and the 2nd largest is 2.

add 10 add 3 big 1 -> 10 big 2 -> 3 big 3 -> none del 3

## Why this is not problem 925 again

Problem 925 asks for the kth largest of a stream that only ever GROWS, which is why a heap of size k solves it: once the heap is full, every arrival either falls out immediately or pushes the smallest of the k out, and the smallest of the k is the answer. That argument collapses the moment a del can take out a key the heap has already discarded, because the heap has no way to get it back.

So the structure here has to hold everything and still answer by rank.

## What most people try first

Keeping a second structure for the largest keys, or sorting on every query. Sorting is O(q log q) per query and so O(q^2 log q) overall, which 200000 operations does not survive.

## The method: one rank question, asked from the other end

Every operation is read before the first one is executed, so every value that can ever be stored is known in advance. Compress them, keep a Fenwick tree of how many copies of each compressed value are stored, and note that with m keys stored

the kth largest = the (m - k + 1)th smallest

m = 3, keys 2 2 5 k = 1 -> smallest rank 3 -> 5 k = 2 -> smallest rank 2 -> 2 k = 3 -> smallest rank 1 -> 2

and the (m - k + 1)th smallest comes out of one binary descent of the tree.

## Why the conversion is correct

Line the m stored keys up in sorted order. Counting from the left, a key at position p has exactly p - 1 keys before it; counting from the right it has m - p keys after it, so it is the m - p + 1th largest. Setting k = m - p + 1 and solving gives p = m - k + 1. The argument never mentions distinct values, which is why duplicates need no special case.

## The boundary that breaks a careless implementation

Off by one in m - k + 1. Writing m - k answers the k + 1th largest, and it is right exactly when k = m, so a test that only ever asks for the largest and the smallest passes it. Guard k against m BEFORE converting, too, or k > m produces a non-positive rank that a descent will happily turn into the smallest key.

## Cost

O(q log q) time and O(q) memory. A key of 10^9 fits in a signed 32 bit integer, whose limit is 2147483647, and m is at most q = 200000.

Constraints - `1 ≤ q ≤ 200000` - `-1000000000 ≤ v ≤ 1000000000` - `0 ≤ k ≤ 200000` - A `del v` always names a value with at least one copy currently stored. - Every operation is `add v`, `del v` or `big k`. - Every value that can ever be stored appears in the input, so the values are known in advance.