← 返回题目列表

Codeforces · 2148/E

E. 分裂

中文机器翻译题面 查看原题

Farmer John 有一个数组 $$$a$$$,其中包含 $$$n$$$ 正整数和一个整数 $$$k$$$。

令 $$$a[l, r]$$$ 为 $$$a$$$ 的子数组$$$^{\text{*}}$$$。他执行以下过程来独立确定子数组 $$$a[l, r]$$$ 是否很棒:

  • 最初,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$$$).
  • 子数组 $$$a[l, r]$$$ 非常棒,如果有某种方法可以让他放置元素,使得对于每个值 $$$v$$$,所有多重集都包含相同数量的值为 $$$v$$$ 的元素。换句话说,他想让所有多重集包含完全相同的元素(忽略顺序)。

输出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 \le 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 子数组的数量。

示例

输入
复制

4
3 2
1 1 1
4 2
1 2 1 2
8 2
3 3 3 3 2 2 2 2
6 3
1 1 1 1 1 1

输出
复制

0
7
18
11

注意

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

对于 $$$k=2$$$,您无法在两个多重集中以相同数量的 $$$1$$$ 结束,因此子数组不起作用。

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

对于 $$$k=2$$$,最终状态必须为每个多重集恰好提供一个 $$$1$$$ 和一个 $$$2$$$。因此,一个有效的子数组可以包含 最多 1 个 $$$1$$$ 和 最多 1 个 $$$2$$$.