2256. Pair Off the Two Ends

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 pair remove ONE copy of the smallest stored key and ONE copy of the largest, and print the sum of the two keys; print the word thin if fewer than two copies are stored

add 10 add 3 add 7 copies 3 7 10 pair -> 13 removes 3 and 10, leaving 7 pair -> thin only one copy left add 1

A collection of exactly two copies of the same value still pairs: the smallest and the largest are both that value, two copies go, and the sum is twice it.

## What most people try first

Two heaps, a min-heap and a max-heap over the same values. It handles pair well and nothing else: the copy removed from the min-heap is still sitting in the max-heap, and a binary heap cannot reach into its middle to take it out. The usual repair is lazy deletion, keeping a count of what should have gone and discarding stale tops, which works here and gets steadily harder to reason about as soon as anything else has to be answered about the collection.

The second instinct is a sorted array, taking the two ends. The ends are the cheap part of an array and add is not: inserting into the middle is O(q), which is up to 2 * 10^10 element moves across 200000 operations.

## The method

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

if m < 2 -> thin lo = value at the position of the 1st smallest copy (one descent) hi = value at the position of the mth smallest copy (one descent) print lo + hi remove one copy of lo, then one copy of hi

Both ends are rank queries, which is why one structure answers both: rank 1 is the smallest and rank m is the largest.

## Why both values must be read before either removal

hi is the mth smallest, and removing a copy of lo changes m. Reading hi after that removal asks for rank m of a collection with m - 1 copies, which the guard turns into nothing or, unguarded, into the wrong key. Reading both first makes the two removals independent, and they are legitimate independently because m >= 2 means there really are two distinct copies to take, even when they hold the same value.

## The case that catches almost everyone

Two copies of one value. lo and hi are then the same number, the sum is twice it, and TWO copies have to go. An implementation that removes lo and then checks whether hi == lo to avoid a double removal leaves a copy behind and reports thin one operation late. An implementation that erases the whole value instead of one copy of it empties a triple when it should leave one.

## Overflow

The two keys are each at most 10^9 in magnitude, so the sum is at most 2 * 10^9 in magnitude. The signed 32 bit range runs to 2147483647, so 2 * 10^9 still fits, and this problem does NOT need 64 bit arithmetic. It is worth checking rather than assuming: the sum of two values in this range is the largest quantity the problem forms, and 2 * 10^9 is below the limit by about 147 million.

## Cost

O(q log q) time and O(q) memory: two descents and two updates per pair.

Constraints - `1 ≤ q ≤ 200000` - `-1000000000 ≤ v ≤ 1000000000` - Every operation is `add v` or `pair`. - Every value that can ever be stored appears in the input, so the values are known in advance.