CF2148E.Split

农夫 John 有一个包含 $n$ 个正整数的数组 $a$ 和一个整数 $k$。

记 $a[l, r]$ 表示数组 $a$ 的一个子数组$^{\text{∗}}$。他执行如下过程来独立判断子数组 $a[l, r]$ 是否为“awesome”：

• FJ 最初有 $k$ 个空的多重集，编号从 $1$ 到 $k$。
• 对于 $a$ 中的每一个元素 $a_i$（$1 \leq i \leq n$）：
  • 如果 $l \leq i \leq r$（也就是 $a_i$ 属于子数组 $a[l, r]$），他将 $a_i$ 放入多重集 $1$；
  • 否则，他可以随意将 $a_i$ 放入任意一个多重集（可以是多重集 $1$）。
• 如果存在一种分配方式，使得对于每个取值 $v$，所有多重集中值为 $v$ 的元素个数都相同，也就是说，使得所有多重集中包含完全相同的元素（忽略元素顺序），则称子数组 $a[l, r]$ 为“awesome”。

请输出所有“awesome”子数组的数量。

$^{\text{∗}}$ 对于大小为 $n$ 的数组 $a$，以及整数 $1 \leq l \leq r \leq n$，子数组 $a[l, r]$ 是由 $a_l,\ldots,a_r$ 按顺序组成的数组。

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \leq k \leq n \leq 2 \cdot 10^5$）。

接下来一行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示“awesome”子数组的数量。

测试用例 1：$n=3$，$a=[1,1,1]$。

对于 $k=2$，无法让两个多重集中 $1$ 的数量相等，因此没有“awesome”子数组。

测试用例 2：$n=4$，$a=[1,2,1,2]$。

对于 $k=2$，最终状态下每个多重集都应包含恰好一个 $1$ 和一个 $2$。因此，一个有效的子数组最多只能包含一个 $1$ 和最多一个 $2$。

由 ChatGPT 5 翻译