1921. Two Tiers and One Promotion Rule

A cache has two tiers: a FAST one holding at most c1 entries and a SLOW one holding at most c2. A key lives in exactly one tier or in neither. Two operations arrive, one per line:

put k v store v under k get k report which tier answered, and the value

A get prints fast and the value, or slow and the value, separated by one space, naming the tier the key was FOUND in. A key in neither prints miss.

c1 = 1, c2 = 2 put 1 10 fast holds 1 put 2 20 2 enters fast, 1 is demoted to slow get 1 -> slow 10 found in slow, then promoted to fast, which demotes 2 to slow get 2 -> slow 20 get 1 -> fast 10

## The rules, in the order they apply

Each tier is independently least-recently-used, and a successful get counts as a use in whichever tier held the key.

1. put k v on a key already in the FAST tier overwrites the value and makes it the most recently used there. Nothing else happens. 2. put k v on a key in the SLOW tier removes it from there and inserts it into the fast tier as the most recently used. 3. put k v on a key in neither tier inserts it into the fast tier as the most recently used. 4. get k on a key in the slow tier PROMOTES it: it leaves the slow tier and enters the fast tier as the most recently used. The answer still says slow, because that is where it was found. 5. After any insertion into the fast tier, if the fast tier now holds more than c1 entries, its least recently used entry is DEMOTED to the slow tier as the slow tier's most recently used. If the slow tier then holds more than c2, its least recently used entry is dropped entirely.

Step 5 is the part that has to be stated. A promotion is not just a move, it pushes somebody down, and the entry it pushes down may push somebody out.

## What most people try first

Two independent caches with a lookup that tries one and then the other. That is the right skeleton and it is wrong in one specific place: promoting on a slow hit without demoting from the fast tier, so the fast tier quietly grows past c1 and the cache stops behaving like a cache at all. The counts only disagree once a slow hit happens while the fast tier is full, which casual test data rarely reaches.

The other first attempt scans a list to find the least recently used entry when a demotion is needed. That is O(c1) per promotion, about 4 * 10^10 steps with c1 and q both at 2 * 10^5.

## The structure

fast doubly linked list of keys, most recently used at the front slow the same, separately where one map from key -> (which tier, which node)

One map rather than two, because a key is in at most one tier and the map can record which. Every step above is then a constant number of unlinks and re-inserts, with the demotion victim read from the back of the fast list rather than searched for.

## Why the cascade terminates and why it is enough

An insertion adds exactly one entry to the fast tier, so step 5's first check fires at most once and moves exactly one entry down. That move adds exactly one entry to the slow tier, so the second check also fires at most once. So the cascade is two conditional moves, not a loop that can run long, and the two invariants size(fast) <= c1 and size(slow) <= c2 hold again at the end of every operation because they held at the start and only one entry entered each tier.

## Sizes

Keys and values reach 10^9, inside a signed 32 bit integer whose limit is 2147483647, and nothing here adds two of them. Every operation is O(1), so the run is O(q) with O(c1 + c2) memory.

Constraints - `1 ≤ c1 ≤ 200000` and `1 ≤ c2 ≤ 200000` - `1 ≤ q ≤ 200000` - `1 ≤ k ≤ 1000000000` - `0 ≤ v ≤ 1000000000` - both tiers start empty