Hidden Knowledge of the Ancients

We need count subarrays satisfying two things:

• exactly $k$ distinct values
• length between $l$ and $r$

Trying to maintain both “exactly $k$” and “length in range” directly is doable, but it gets fiddly. The clean trick is to count a softer condition and subtract.

Step 1: Replace exactly with at most

Let:

$$G(K, X) = \text{number of subarrays with at most } K \text{ distinct values and length at most } X$$

Then the number of subarrays with exactly $k$ distinct values and length at most $X$ is:

$$G(k, X) - G(k-1, X)$$

Because at most k includes everything with $0,1,2,\dots,k$ distinct values, and at most k-1 removes all the ones that are not exactly $k$.

Now we also need length between $l$ and $r$, so subtract the ones with length at most $l-1$:

$$\text{answer} = (G(k,r)-G(k-1,r)) - (G(k,l-1)-G(k-1,l-1))$$

Rearranged:

$$\boxed{G(k,r)-G(k,l-1)-G(k-1,r)+G(k-1,l-1)}$$

That is the whole math. Not magic, just subtraction doing unpaid labor.

Step 2: Compute $G(K, X)$ with two pointers

We need count subarrays with:

• at most $K$ distinct values
• length at most $X$

Fix the right endpoint right.

Maintain a sliding window [left, right] such that it has at most $K$ distinct values. When adding a[right] makes the distinct count too large, move left forward until the window is valid again.

After that, every start position s >= left gives a subarray [s, right] with at most $K$ distinct values.

But we also need length at most $X$:

$$right - s + 1 \le X$$

So:

$$s \ge right - X + 1$$

Therefore the valid starts for this right are:

$$s \in [\max(left, right-X+1), right]$$

The number of those starts is:

$$right - \max(left, right-X+1) + 1$$

if the interval is nonempty.

Since left <= right after the sliding window is fixed, and $X \ge 1$ for real calls, this formula works cleanly. For safety, return 0 when $K \le 0$ or $X \le 0$.

Coordinate compression

The values $a_i$ can be up to $10^9$, so using them directly as indices would be dumb. Compress them to 0..m-1, then use a frequency vector.

Complexity

Each call to $G$ moves each pointer at most $n$ times, so it is $O(n)$ after compression.

We call it four times, still $O(n)$ per test case. Compression costs $O(n \log n)$.

Total complexity:

$$O(n \log n)$$

per test case, with total $n \le 2\cdot 10^5$, easily fine.