Split

Let $cnt[v]$ be the number of times value $v$ appears in the whole array.

For the final $k$ multisets to be identical, each value must be split equally among them. That means $cnt[v]$ must be divisible by $k$ for every $v$. If even one value fails this, the answer is $0$. No clever placement saves you there; arithmetic already killed the plan.

Now suppose every value passes divisibility.

Then each multiset must contain exactly

$$lim[v] = \frac{cnt[v]}{k}$$

copies of value $v$.

For a subarray $a[l,r]$, all its elements are forced into multiset $1$. So if this subarray contains $x[v]$ copies of value $v$, we must have

$$x[v] \le lim[v]$$

for every value $v$. Otherwise multiset $1$ already has too many copies of $v$, and we cannot remove them. Game over.

The important part: this condition is also sufficient.

If the subarray uses $x[v]$ copies of $v$ in multiset $1$, then outside the subarray there are $cnt[v]-x[v]$ remaining copies. We need to put:

• $lim[v]-x[v]$ more copies into multiset $1$,
• $lim[v]$ copies into each of the other $k-1$ multisets.

The total needed outside is

$$(lim[v]-x[v]) + (k-1)lim[v] = klim[v]-x[v] = cnt[v]-x[v],$$

which is exactly how many outside copies exist. Since values are independent, we can do this for every value separately.

So the whole multiset story collapses into a much cleaner problem:

Count subarrays where every value $v$ appears at most $lim[v]$ times.

That is a standard sliding window.

Maintain a window $[L,R]$ and current frequencies inside it. When we add $a[R]$, only that value's frequency can become invalid. If it exceeds its limit, move $L$ right, subtracting frequencies, until the window is valid again.

After fixing the window for this $R$, every subarray ending at $R$ and starting at any position from $L$ to $R$ is valid. There are

$$R-L+1$$

such subarrays, so add that to the answer.

Why are all those suffixes valid? Because removing elements from a valid window can only decrease frequencies. It cannot create a new violation. Pretty nice when the problem stops pretending to be about $k$ multisets and admits it's just frequency caps.

Complexity is $O(n)$ per test case, since each pointer moves right at most $n$ times. Memory is $O(n)$ because values are between $1$ and $n$.