2263. The Two Ends at Once

A collection of integers starts empty and may hold several copies of the same value. 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 ends print the smallest stored key and the largest stored key, separated by a single space, or none none when nothing is stored

add 10 ends -> 10 10 one key is both ends add 3 ends -> 3 10 del 10 ends -> 3 3

## Why a heap cannot do this and two heaps barely can

A priority queue knows one end. Getting both means two heaps over the same values, and then del breaks them: the copy removed from one heap is still in the other, and a binary heap cannot reach into its middle to take it out. The standard repair is lazy deletion, a tally of copies that should already be gone plus a clean-up pass before every read, which works and means neither heap can be trusted without first cleaning it.

Problems 891 and 921 are the versions of this that only ever need the maximum, which is precisely why one heap is enough there.

## What most people try first

Two running variables, a minimum and a maximum, updated on every add. They are correct until the first del: removing the current minimum leaves the variable holding a key that is no longer stored, and there is nothing in a scalar to fall back to. A rescan to repair it is O(m), so O(q^2) across the run.

## The method: both ends are ranks

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

m == 0 -> none none smallest = the 1st smallest copy (one binary descent) largest = the mth smallest copy (one binary descent)

One structure, two descents, and no clean-up pass anywhere.

## Why rank m is the largest

Ranks run from 1 to m over the stored copies in increasing order, so rank m is the last of them, which is the largest. Note that both ends are the SAME key when m == 1, and when every stored copy holds one value: three copies of 2 print 2 2, since rank 1 and rank 3 both land on 2. The ranks are over copies, not over distinct values, so nothing special is needed for that.

## The boundary that breaks a careless implementation

The empty collection. Rank 1 and rank m are both invalid when m is 0, and the output is the two words none none rather than an empty line or a single none, which a judge comparing bytes will not forgive. And m must be maintained on del as well as add, or rank m points past the end of the collection and an unguarded descent returns the largest key that was ever stored rather than the largest one still there.

## 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 nothing here adds two keys together.

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