← 返回题目列表

Codeforces · 2149/E

E. 古人的隐藏知识

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

在世界上 深度觉醒,存在一件远古神器—— 无限知识平板,上面刻有一系列$$$n$$$神秘符号(每个符号都是一个整数)。

据说,只有找到所有物品才能揭示该神器的真正威力。 神圣碎片 — 包含精确 $$$k$$$ 不同数字的平板电脑的连续段,其长度必须在 $$$l$$$ 和 $$$r$$$ 之间(包含)。

形式上:给定一个长度为 $$$n$$$ 的序列 $$$a$$$ 和整数 $$$k$$$、$$$l$$$、$$$r$$$。您需要找到此类边界 $$$b$$$ 和 $$$c$$$ 的数量,以便:

  • $$$1 \le b \le c \le n$$$;
  • 在元素 [$$$a_{b}, a_{b + 1}, \dots, a_{c}$$$] 中,正好有 $$$k$$$ 不同的数字;
  • $$$l \leq c - b + 1 \leq r$$$。

输入

每个测试由多个测试用例组成。

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

下面介绍测试用例。

每个测试用例的第一行包含四个整数:$$$n$$$、$$$k$$$、$$$l$$$ 和 $$$r$$$ $$$( 1 \le k \le n \le 2 \cdot 10^5, 1 \le l \le r \le n)$$$。

第二行包含 $$$n$$$ 数字 $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — 神秘符号。

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

输出

对于每个测试,在单独的行上输出一个整数 - 满足指定条件的连续子​​数组的数量。

示例

输入
复制

5
1 1 1 1
5
5 2 2 3
1 2 1 3 2
6 3 1 6
1 2 3 1 2 3
4 1 1 2
7 7 7 7
7 3 2 4
1 2 1 2 3 2 1

输出
复制

1
5
10
7
5

注意

在第一个测试用例$$$a=[5]$$$中,只有一个子数组$$$[5]$$$,其长度为1并且恰好包含$$$1$$$不同的数字。

在第四个测试用例 $$$a=[7,7,7,7]$$$ 中,任何相同数字的子数组都给出精确的 $$$1$$$ 不同数字。可能的子数组的开头和结尾是:

  • 长度$$$1$$$:$$$[1,1]$$$、$$$[2,2]$$$、$$$[3,3]$$$、$$$[4,4]$$$。
  • 长度$$$2$$$:$$$[1,2]$$$、$$$[2,3]$$$、$$$[3,4]$$$。
总计:$$$7$$$。

在第五个测试用例 $$$a=[1,2,1,2,3,2,1]$$$ 中:

  • 长度 $$$2$$$:所有子数组只有 $$$2$$$ 不同的数字。
  • 长度$$$3$$$:$$$[3,5]$$$,$$$[5,7]$$$。
  • 长度$$$4$$$:$$$[2,5]$$$、$$$[3,6]$$$、$$$[4,7]$$$。
总计:$$$5$$$。