2264. The Closest Two Values So Far
n values arrive one at a time. After each arrival, print the smallest
absolute difference between any TWO of the values that have arrived so far.
The first arrival has nothing to pair with, so its line is the word none.
Two equal values have a difference of 0, and equal values are allowed.
``` arrivals 10 3 7 8
after 10 -> none after 3 -> 7 the only pair after 7 -> 3 3 and 7 beat 10 and 3 after 8 -> 1 7 and 8 ```
## What most people try first
Sorting the values and scanning neighbouring pairs. That is the right idea and
it answers the WRONG question: it gives the smallest difference in the whole
row, once, while this asks for the answer after each of the n prefixes. Doing
the sort again per prefix is n sorts, O(n^2 log n), and comparing all pairs
of each prefix is O(n^3). Problem 256 is the single-answer version, and it is
worth solving first to see that this one is not it.
## The only pair worth looking at
When a new value v arrives, every pair that does not involve v was already
considered on an earlier line. So the answer is the previous answer, possibly
improved by a pair that uses v. And among the values already present, the one
closest to v is either the largest below it or the smallest above it:
best = min(best, v - predecessor(v), successor(v) - v)
## Why the two neighbours are enough
Take any stored value x below v. The predecessor p is the largest stored
value below v, so p >= x, so v - p <= v - x. The same argument above v
gives the successor, and every stored value is on one side or equal. An equal
value makes the difference 0, which is the smallest possible, so it is handled
by checking the count of v first and answering 0.
So two queries and one insertion per arrival, with the running minimum carried across the steps. Every value is read before the first answer is produced, so every value that can ever be stored is known in advance. Compress them and keep a Fenwick tree of counts over the compressed positions.
## Why the answer never increases
Nothing is ever removed here, so the set of pairs only grows and its minimum only falls. That makes the running minimum a single variable, and it is the one property that pattern 6's second problem deliberately takes away.
## The boundary that breaks a careless implementation
The first line, which must be none and not 0 and not the initial value of
the running minimum. Printing the sentinel is the common bug and it is invisible
unless a test has n = 1, so there is one.
## Cost
O(n log n) time and O(n) memory. Values reach 10^9 in magnitude, so a
difference reaches 2 * 10^9, which is 2000000000. The limit of a signed 32 bit
integer is 2147483647, so the differences fit, and so does the sentinel the
running minimum starts at, since it only has to EXCEED the largest difference
and 2000000001 is still inside the limit. Nothing accumulates here, so 32 bits
is genuinely enough, with about 147 million to spare.
The way to get this wrong is to reach for a round sentinel like 4 * 10^9,
which does not fit and which Java will not even accept as a literal without a
long suffix. Pick the sentinel from the bound, not from habit.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - Values may repeat. - Every arrival is given before any answer is required, so the values are known in advance. - The intended cost is `O(log n)` per arrival.
Input
The first line contains one integer n.
Each of the next n lines contains one integer, the value arriving at that step.
Output
Print n lines. Line i holds the smallest absolute difference between two of the first i arrivals, except line 1, which holds the word none because one value makes no pair.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.