199. An LRU Cache
A cache holds at most c entries. When it is full and a NEW key is stored,
the LEAST RECENTLY USED entry is evicted to make room.
Both storing and reading count as using an entry, so a read moves that key to the most recently used position.
Every operation must be constant time, scanning for the oldest entry on each eviction is too slow. This is a real structure: your browser, your operating system's page cache and every database use it.
Constraints - `1 ≤ c ≤ 100000` - `1 ≤ q ≤ 200000` - `1 ≤ k ≤ 1000000` - `0 ≤ v ≤ 1000000`
Input
The first line contains two integers c and q, the capacity and the number of operations.
Each of the next q lines is one operation:
- 1 k v, store value v under key k
- 2 k, read the value stored under key k
Output
Print one line for each 2 operation, the stored value, or -1 if that key is not in the cache.
A 1 operation prints nothing. Stored values are never negative, so -1 always means "not found".
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.