719. The Median of Every Window
k is ODD. For every window of k consecutive values, print its MEDIAN, the value that would
sit in the middle if the window were sorted.
1 3 2 3 5 3 6 7, k = 3 -> 2 3 3 3 5 6
7 1 7 1 7, k = 3 -> 7 1 7
1 2 3 4 5, k = 3 -> 2 3 4
## Why the usual tools fail
A running sum survives a value leaving; a median does not. Two heaps track a median as values ARRIVE (problem 870 does exactly that), but a window also needs values to LEAVE, and a binary heap cannot remove from the middle.
A monotonic deque is no help either: it answers "maximum" or "minimum", not "the value at rank
r". This is the point at which the deque family runs out, and knowing where a tool stops is
as useful as knowing how it works.
## Ranks over a bounded value range
The values are at most 2000, so keep a COUNT per value and a Fenwick tree over those counts.
The tree gives two operations in O(log V):
· add or remove one occurrence of a value
· find the smallest value whose cumulative count reaches r
The median is the value at rank k/2 + 1 with integer division, so it is the second operation
with r = k/2 + 1.
Trading an unbounded structure for a bounded value range is the move. It is available whenever the statement caps the values, and it is worth looking for that cap before reaching for anything heavier.
## Finding the rank without a second loop
Descend the Fenwick tree by powers of two, largest first:
pos = 0; rem = r; step = highest power of two <= V
while step > 0:
if pos + step <= V and tree[pos + step] < rem:
pos += step
rem -= tree[pos]
step /= 2
answer = pos + 1
This lands on the last value whose cumulative count is still BELOW r, so the answer is one
past it. A linear scan of the counts would be O(V) per window, which is 4 * 10^8
operations at the limits.
## The shape of the loop
Add a[i], remove a[i-k] once i >= k, and report from i >= k-1 onward. The window is
not k wide before that.
## Boundaries
k = 1 reprints the array. k = n prints one value. All values equal prints that value every
time.
## Cost
Time O(n log V). Space O(V).
Constraints - `1 ≤ k ≤ n ≤ 200000` - `k` is odd - `1 ≤ each value ≤ 2000`
Input
The first line contains two integers n and k, with k odd.
The second line contains n integers.
Output
Print the n - k + 1 medians on one line, separated by spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.