1926. A Stack With a Bulk Increment Nobody Pays For

Build a stack with four operations, one per line:

push v put v on top, printing nothing inc k x add x to each of the BOTTOM k entries, printing nothing pop remove the top entry and print its current value top print the top entry's current value without removing it

8 push 1 -> push 2 -> push 3 -> the stack, bottom to top, is 1 2 3 inc 2 100 -> the bottom two become 101 102 top -> 3 the third entry was not touched pop -> 3 pop -> 102 pop -> 101

## The rules, stated so the answer is decidable

• push and inc print nothing. pop and top each print one line.
• pop and top on an empty stack print empty and change nothing.
• If k exceeds the number of entries held, inc adds x to ALL of them. If
• k is 0, or the stack is empty, inc changes nothing. Both cases are
• legal input, not errors.
• inc counts from the BOTTOM. The bottom entry is the oldest one still held.
• A later push is unaffected by earlier increments. Adding to the bottom two
• entries and then pushing gives a new entry holding exactly the value pushed.

## What most people try first

Walk the bottom k entries and add x to each. That is correct and it is O(k). With q at 2 * 10^5, half of it pushes and half of it inc with k at the full height, that is about 5 * 10^9 additions.

The instinct that follows is to keep one global offset added to everything. That fails immediately, because inc touches a PREFIX of the stack, not all of it, and the next push must not inherit the offset.

## Owe the increment to a depth

Keep a second array the same height as the stack. Entry lazy[j] means "every entry at depth 0 through j is owed this much, and it has not been paid".

inc k x: j = min(k, height) - 1; if j >= 0 then lazy[j] += x top: value = vals[top] + lazy[top] pop: value = vals[top] + lazy[top] then lazy[top - 1] += lazy[top] pass the debt downwards then drop both top entries

## Why it is correct

The invariant is: the true value of the TOP entry is always vals[top] plus lazy[top], and every debt owed to an entry deeper than the top is recorded at some depth at or above that entry.

inc k x records the debt at the deepest entry it covers, so it covers exactly depths 0 through j, which is the prefix asked for. A push appends a fresh pair with lazy zero, so the new entry is owed nothing, which is the rule about later pushes. A pop is the only place the invariant could break: the debt recorded at the top depth also covered everything below it, so before the top is discarded that debt is handed to the new top. By induction the new top's own lazy entry then accounts for every debt that still applies to it.

Nothing is ever read except the top, which is the reason one number per depth is enough: a debt only has to be correct by the time its depth becomes the top.

## Overflow

A single value is at most 10^9 and a single x is at most 10^9, both of which fit in a signed 32 bit integer since the limit is 2147483647. The ACCUMULATION does not. With q at 2 * 10^5 almost all of it inc 1 1000000000, one entry can be owed 2 * 10^14. Use 64 bit integers for the values and for lazy. In JavaScript 2 * 10^14 is still exact as a plain number, since that is well under 2^53, so no BigInt is needed, but any bitwise operator would truncate to 32 bits and must be avoided.

## Cost

O(1) per operation, with memory proportional to the height.

Constraints - `1 ≤ q ≤ 200000` - `0 ≤ v ≤ 1000000000` - `0 ≤ k ≤ 200000` - `0 ≤ x ≤ 1000000000` - the stack starts empty - each of `push`, `inc`, `pop` and `top` must run in `O(1)`, so the whole run is `O(q)` - the judge cannot enforce that: the declared tests are small and there is no test generator yet, so walking the bottom `k` entries passes them. At `q = 200000` with a full-height `inc` every other line that walk does about `5 * 10^9` additions, which is the bound the contract is about