688. Stretches Holding the Largest Value k Times
Let M be the LARGEST value in the whole array. Count the contiguous stretches that contain
at least k copies of M.
1 3 2 3 3, k = 2 -> 6 M = 3
3 1 3 1 3, k = 2 -> 5
1 4 2 1, k = 3 -> 0
5 5 5, k = 1 -> 6
## The array maximum is fixed before the sweep starts
M is the maximum of the ENTIRE array, not of the stretch. So one pass finds it, and from
then on every value is simply "is it M or not". The problem collapses to counting stretches
that contain at least k marked positions.
Recognising that the interesting quantity is global and can be computed once, rather than maintained per window, is the first move.
## Count by right end, and remember where the marks are
Fix a right end hi. A stretch lo .. hi qualifies when it holds at least k marks. The
marks up to hi, in order, sit at positions p[0] < p[1] < ... < p[t-1].
To hold k of them, the left end must be at or before the k-th mark counted BACKWARDS from
hi, which is p[t - k]. Every lo from 0 to p[t - k] works, so this right end
contributes p[t - k] + 1 stretches.
for hi in 0 .. n-1:
if a[hi] == M: p.append(hi)
if len(p) >= k: answer += p[len(p) - k] + 1
## Why that index and not another
p[t - k] is the EARLIEST mark the window may exclude nothing of: keeping it and everything
after gives exactly k marks. Take lo one position further right, past that mark, and only
k - 1 remain.
Off by one here is the whole difficulty. Check it on 3 1 3 1 3 with k = 2: at hi = 4
the marks are 0, 2, 4, so p[3 - 2] = p[1] = 2 and this right end contributes 3.
## An equivalent way to say the same thing
Instead of the list, keep a left pointer that advances until the window holds exactly k - 1
marks, and add its position. Both are linear, and both hinge on the same observation: the
qualifying left ends form a PREFIX of the positions, so they can be counted rather than
enumerated.
## Boundaries
k larger than the number of copies of M gives 0, and 1 4 2 1 with k = 3 is that
case: there is one 4.
All values equal makes every position a mark, so k = 1 gives n * (n + 1) / 2.
## Overflow
With every value equal and k = 1 the answer is about 2 * 10^10, past a signed 32 bit
integer. The trap is in the ANSWER, not in anything the loop computes.
## Cost
Time O(n). Space O(n) for the positions, or O(1) with the pointer form.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 200000` - `1 ≤ each value ≤ 10^9`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print one integer, the number of stretches holding at least k copies of the array maximum.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.