1914. Insert, Remove and Pick in Constant Time

Build a set supporting three operations, each in constant time on average:

insert x add x; print YES if it was not already present, otherwise NO remove x remove x; print YES if it was present, otherwise NO pick i print the element at position i of the current contents

i is a 0-based index, guaranteed to be valid at the time it runs. A real version of this structure would return a uniformly random element; an index makes the same requirement testable without any randomness, because it still demands storage you can index.

The order is pinned by the method below: insert appends, and remove moves the LAST element into the vacated slot. pick must report the element at index i of that arrangement.

## What most people try first

One structure. A hash set, because insert and remove are what a hash set is for, and then pick i has nothing to index: a hash set has no positions, and its iteration order is not a contract you may lean on.

An array instead, and the opposite happens. pick i is one read, and remove has to find the value and then close the hole by shifting everything after it. That is O(n) per removal, so 200000 removals from the front cost about 2 * 10^10 element moves. Neither structure is wrong; neither answers all three questions.

## An array plus a position map

Keep both, and make them describe each other:

``` vals an array of the values, in no meaningful order pos a map from value -> its index in vals

insert x: if x in pos -> NO pos[x] = len(vals); vals.append(x); YES

remove x: if x not in pos -> NO i = pos[x]; last = vals[-1] vals[i] = last; pos[last] = i vals.pop(); del pos[x] YES

pick i: vals[i] ```

The hole is closed by moving one element rather than by shifting many, which is the whole trick: order is sacrificed and cost becomes constant.

## Why it is correct

The invariant is that pos[v] == j exactly when vals[j] == v, for every value present. insert writes both halves before anything reads them. remove repairs the only two entries it could have broken: vals[i] now holds last, so pos[last] is set to i, and x is gone, so its key is deleted. Because the invariant holds at every boundary, membership can always be decided in constant time and every index in 0 .. len(vals) - 1 holds a present value, which is what makes pick well defined.

## The boundary that breaks a careless implementation

Three cases, each with a test. Removing the LAST element makes last the element being removed, so the swap is with itself and the order of the two writes decides whether the map ends up holding a key that is no longer there. Removing from the middle is the case the swap exists for. Deleting x from the map before writing pos[last] loses the repair when x == last.

Forgetting pos[last] = i altogether is the quiet one: everything still looks right until that moved element is removed later, at which point the write lands on a stale slot or past the end of the array.

## Overflow

A value reaches 1000000000 in magnitude, which fits in a signed 32 bit integer. The values here are only keys and payload: they are stored, compared for equality and printed, never summed, so nothing widens. Zero is a legal value and must not be read as "absent", which is a representation bug rather than an arithmetic one and has its own test.

## Cost

O(1) expected for all three operations, and O(n) memory. The judge cannot enforce that, so the shifting array passes every declared test; the 2 * 10^10 figure above is what it costs at the stated limit.

Constraints - `1 ≤ q ≤ 200000` - `-1000000000 ≤ x ≤ 1000000000` - Every `pick` index is valid at the time it runs.