2231. The First Free Locker From Here On

A row of n lockers numbered 1 to n all start free. Then q operations arrive, one per line:

take v assign the smallest FREE locker numbered v or higher, print its number, and mark it taken; print full if every locker from v upwards is taken free v mark locker v free again; it is guaranteed to be taken

Print one line for every take.

5 lockers take 1 -> 1 take 1 -> 2 take 1 -> 3 free 2 take 1 -> 2 locker 2 is free again and is the smallest from 1 up

## The complexity contract

take O(log n) free O(log n)

## Keep the FREE lockers, not the taken ones

That is the whole problem. The natural reading stores which lockers are taken, and then take v has to scan upwards from v looking for a gap, which is O(n) in the worst case and O(n q) over the stream, up to 4 * 10^10 steps at the limits.

Store the FREE lockers instead and the question becomes one ordered-set lookup:

take v: c = ceiling of v in the set of free lockers full if there is none, otherwise print c and remove it free v: insert v

So the structure answers "the smallest free locker at least v" directly, because that is exactly a ceiling query on the free set. Turning a scan into a lookup by storing the complement is the move worth remembering.

## Why the universe is known here without reading the queries

The other problems in this topic say that all the values are known in advance because every operation is read before the first one runs. This one does not need that argument: the lockers are numbered 1 to n and n is given on the first line, so the universe is 1..n and nothing has to be compressed at all.

That makes the Fenwick tree particularly direct: one entry per locker, holding 1 when free and 0 when taken.

## The method

cnt is a Fenwick tree over 1..n, every entry 1 at the start, total = n take v: c = prefix(v - 1) how many free lockers are below v if c == total: print full else: g = the (c + 1)-th free locker, by one binary descent print g; set cnt[g] = 0; total = total - 1 free v: set cnt[v] = 1; total = total + 1

The (c + 1)-th free locker is the ceiling: there are c free lockers strictly below v, so the next one in order is the first at or above v.

## Why the answer is never below v, and never skips a free locker

Both directions matter and both are one line. The (c + 1)-th free locker is not below v because exactly c free lockers are, and it is the smallest such because the free lockers are enumerated in increasing order by the descent. So no free locker between v and the answer can have been missed.

## What full means, and what it does not

full means every locker from v upwards is taken. It does NOT mean the whole row is taken: take 3 can print full while lockers 1 and 2 are free. The declared test 3 lockers, take 3, take 3, free 3, take 3 shows that, and a solution that compares the total against n instead of against the prefix below v gets it wrong.

## Cost

O((n + q) log n) time and O(n) memory. Locker numbers are at most 200000, so every value here fits in a signed 32 bit integer with four orders of magnitude to spare.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `1 ≤ v ≤ n` - Every operation is `take v` or `free v`. - A `free v` is only given when locker `v` is currently taken.