922. The Least-Loaded Machine After Every Update

n machines are numbered 0 to n-1 and start with given loads. Then q updates arrive; each names a machine and a new load for it, replacing whatever that machine held before.

After each update, print the machine with the SMALLEST load and that load. Ties go to the smaller machine number.

``` loads 5 2 9, updates (2 -> 1) (1 -> 8) (0 -> 0) -> "2 1" / "2 1" / "0 0"

loads 7, updates (0 -> 3) (0 -> 3) -> "0 3" / "0 3" ```

## What most people try first

Scanning all n machines after every update is O(nq). At n = 10^5 and q = 2 * 10^5 that is 2 * 10^10.

The textbook answer is an INDEXED heap: a heap that also stores, for every machine, where in the heap its entry sits, so an entry can be found in constant time and then sifted up or down. That gives a genuine O(log n) update, and it is what a priority queue with decrease-key means.

## The honest note about decrease-key

Almost no standard library offers it.

C++ priority_queue has no way to change or remove a stored element Java PriorityQueue.remove(Object) exists and is documented O(n) Python heapq has no removal; its own documentation recommends the lazy scheme below instead JavaScript there is no heap in the standard library at all

Writing an indexed heap by hand is perhaps forty lines and it is the right answer when memory is tight. What people actually write, and what is worth knowing first, is the lazy version.

## The method: version the entries, discard the stale ones

Keep an array cur[i] holding each machine's true current load. Never modify anything inside the heap.

``` cur[i] = the starting load, for every i h = min-heap of (load, machine), seeded with every (cur[i], i)

on update (i, x): cur[i] = x push (x, i) onto h while the top (load, machine) has load != cur[machine]: pop it print the top ```

An entry is STALE exactly when the load it carries no longer matches cur for its machine. Stale entries are left where they are and thrown away only when they reach the top.

## Why it is correct

Claim: after the discard loop, the top of the heap is the true minimum.

Every machine's current (cur[i], i) is somewhere in the heap, because it was pushed either at the start or by the update that set it. So the true minimum is present. Every entry in the heap is either current or stale, and the loop removes stale entries from the top until a current one is exposed. Since the heap orders by (load, machine) and the true minimum is present, nothing current can sit above it, so the first current entry reached is it.

The tie-break falls out of comparing the PAIR rather than the load alone.

## A subtlety worth naming

A machine can be updated back to a value it held before. Then an old entry carrying that same load becomes current-looking again, and both entries are indistinguishable. That is harmless: they carry the same load and the same machine, so whichever is reported gives the same answer. The declared test that sets a machine to 3 twice in a row exists for exactly this case.

## The cost of being lazy, stated plainly

The heap grows to n + q entries rather than n. At the limits that is 3 * 10^5 entries instead of 10^5, so three times the memory, and every entry is pushed once and popped at most once, so the total time is O((n + q) log(n + q)). An indexed heap would hold n entries and do the same number of comparisons. Three times the memory for forty fewer lines is the trade being made, and knowing that it IS a trade is the point.

## The boundary that breaks a careless implementation

The discard loop must run after the push, on every update, and its condition must compare against cur, not against a "deleted" flag. A flag cannot express "this entry was correct once and is not now".

The heap can never empty, because every machine always has a current entry in it, so no emptiness check is needed inside the loop. Adding one hides a bug rather than preventing one.

## Overflow

Loads reach 10^9 and are only ever replaced, never accumulated, so a signed 32-bit integer holds every value in play. Machine numbers reach 10^5. There is no overflow in this problem.

## Related problems

Problem #921 uses the same lazy idea with the staleness recorded in a side map of owed removals, because there the entries carry no identity of their own. Here each entry names its machine, so staleness is decided by one array lookup and no map is needed. Problem #388 runs Dijkstra with a priority queue and is the most common place this pattern appears in practice, since relaxing a vertex is a decrease-key that nobody implements as one.

## Cost

Time O((n + q) log(n + q)). Space O(n + q).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ q ≤ 200000` - `0 ≤ load ≤ 10^9` - `0 ≤ machine number < n`