717. Stretches Holding Enough Matching Pairs
A stretch is GOOD when it contains at least k pairs of positions i < j with equal values.
Count the good stretches.
1 1 1 1 1, k = 10 -> 1
3 1 4 3 2 2 4, k = 2 -> 4
1 1 1 1, k = 2 -> 3
1 2 3, k = 1 -> 0
## Pairs, counted one arrival at a time
When a value arrives and c copies of it are already inside, it forms exactly c new pairs.
So the running pair count is maintained by
pairs += count[v]; count[v] += 1
and, symmetrically, removing a value first decrements its count and then subtracts:
count[u] -= 1; pairs -= count[u]
The order differs between the two, and it has to. On entry the arriving copy pairs with the
c already there; on exit the leaving copy pairs with the c - 1 that remain. Writing both
in the same order is the bug here, and it shows only when a value appears three or more times.
## More is easier, so the left ends form a prefix
Widening a window can only add pairs, never remove them. So for a fixed right end hi there is
a threshold: every left end at or before some position gives a good stretch, and every one
after it does not.
That means the good stretches ending at hi can be COUNTED rather than enumerated, which is
what makes this linear.
## The sweep, and why the answer is lo
Advance lo while the window is still good:
for hi in 0 .. n-1:
pairs += count[a[hi]]; count[a[hi]] += 1
while pairs >= k:
count[a[lo]] -= 1; pairs -= count[a[lo]]; lo += 1
answer += lo
After the loop, lo is the first left end that is NOT good, so the good ones are exactly
0 .. lo-1, and there are lo of them.
Adding lo rather than lo + 1 or hi - lo + 1 is the step to get right. Note this is the
opposite convention to the at-most sweeps in this topic, which add hi - lo + 1: there the
window itself is the legal thing, here everything to the LEFT of it is.
## Boundaries
k larger than the total number of pairs gives 0. 1 1 1 1 1 with k = 10 has exactly
10 pairs in the whole array and none anywhere smaller, so the answer is 1.
## Overflow
The count of good stretches reaches 2 * 10^10, and the pair count inside a window reaches
about 2 * 10^10 as well when every value is equal. Both need 64 bits.
## Cost
Time O(n). Space O(V).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 10^10` - `1 ≤ each value ≤ 2000`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print one integer, the number of good stretches.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.