2266. The kth Different Value in Every Window

n values are given, together with a width w and a rank k. For every window of w consecutive values, print the kth smallest DIFFERENT value the window holds, or the word none when the window holds fewer than k different values. There are n - w + 1 windows, so that is how many lines you print.

Different means counted once however many copies of it the window holds.

``` n = 6, w = 3, k = 2, values 1 2 1 3 3 4

window 1 2 1 different {1, 2} 2nd is 2 window 2 1 3 different {1, 2, 3} 2nd is 2 window 1 3 3 different {1, 3} 2nd is 3 window 3 3 4 different {3, 4} 2nd is 4 ```

## Why this is not problem 191

Problem 191 in the queue topic asks HOW MANY different values each window holds. A map from value to count answers that in O(1) per step with no notion of order at all: when a count rises from 0 the distinct total goes up, when it falls to 0 it goes down. That problem is deliberately there to show that a distinct COUNT needs no ordering.

This asks WHICH different value sits at a given rank, and a count cannot produce it. A rank is an order question. That is the difference the whole topic is about, and this is where it is sharpest: the same bookkeeping that gives 191 its answer in one line gives this one nothing.

## What most people try first

Collecting the window into a set, sorting it, and indexing. Correct, and O(w log w) per window, so O(n w log w) overall, which at n = w = 2 * 10^5 is past 10^10 operations before the logarithm.

The near miss is more interesting: maintaining the window in a Fenwick tree of COUNTS and descending for rank k. That gives the kth smallest value counting copies, which is a different answer. With the window 1 3 3 and k = 2 the counting answer is 3, and it is 3 here too, which is exactly why the bug survives a careless test. With the window 1 1 and k = 2 the counting answer is 1 and the truth is that there is no second different value at all, so the answer is none. That window is a declared test.

## Why this is a sweep and not an operation list

The earlier problems in this topic are driven by a list of operations: the input says add and del and the structure does as it is told. Here the input is a plain row of values and the removals are implied by POSITION, which is what almost every real use of an ordered set looks like.

step i: insert the value arriving at i remove the value that has just fallen out of the window answer the question about what is left

Those three lines must happen in that order. Doing the removal before the insertion, or answering before both, gives a different answer on every window of width 1, which is why the declared tests include one.

## Two trees of the same shape

Every value is read before the first answer is produced, so every value that can ever be stored is known in advance. Compress them. Then keep two Fenwick trees over the compressed positions, updated by the same insert and the same remove:

COUNT tree position p holds how many copies of value p the window has PRESENCE tree position p holds 1 if the window has at least one copy, else 0

The presence tree is maintained from the count: a position's entry becomes 1 when its count rises from 0, and 0 when its count falls back to 0. The answer is then a binary descent down the PRESENCE tree for rank k, which is O(log n).

## Why the descent gives the right value

The presence tree is a Fenwick tree whose prefix sum at p is the number of different values in the window at or below p. That prefix sum is non-decreasing in p and rises by exactly 1 at each present value, so the first p at which it reaches k is the kth smallest present value. The descent finds that p in one walk because a Fenwick tree stores exactly the block sums the walk needs.

When the window holds fewer than k different values the prefix sum never reaches k, and the guard is a single comparison against the presence tree's total, which is problem 191's answer. So 191's answer is a sub-result here rather than a competitor.

## The boundary that breaks a careless implementation

Letting the presence entry fall to 0 while copies remain. With the window 2 2 5 and the leftmost 2 expiring, the count of 2 goes from 2 to 1 and the presence of 2 must stay 1. Flipping it off makes the window look like {5} and every later answer is wrong. The declared tests include windows whose values all repeat.

## Cost

O(n log n) time and O(n) memory. Values reach 10^9 in magnitude, which fits in a signed 32 bit integer whose limit is 2147483647, and nothing here adds two values together: both trees hold counts, which are at most n.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ w ≤ n` - `1 ≤ k ≤ n` - `-1000000000 ≤ a[i] ≤ 1000000000` - Values may repeat, and a repeated value counts once. - `k` may exceed the number of different values in a window, which prints `none`. - The intended cost is `O(log n)` per window.