题目描述

在 Deepwoken 的世界中，存在着一件古老的神器——无限知识石板，上面刻有一串由 $n$ 个神秘符号组成的序列（每个符号为一个整数）。

传说，只有找到所有的神圣碎片，才能揭示神器真正的力量——神圣碎片指的是石板上所有正好包含 $k$ 个不同数字的连续片段，且它们的长度要在 $l$ 到 $r$ 之间（包含 $l$ 和 $r$）。

形式化地说：给定长度为 $n$ 的序列 $a$，以及整数 $k, l, r$，你需要找出所有满足以下条件的边界 $b$ 与 $c$ 的数目：

• $1 \leq b \leq c \leq n$；
• 元素 $a_b, a_{b+1},\dots,a_c$ 恰好包含 $k$ 个不同的数字；
• $l \leq c-b+1 \leq r$。

输入格式

每个测试用例包含多组数据。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的数量。

接下来依次描述每组测试用例。

每组测试用例第一行包含四个整数 $n, k, l, r$（$1 \leq k \leq n \leq 2 \cdot 10^5, 1 \leq l \leq r \leq n$）。

第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 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$ 个。

由 ChatGPT 5 翻译

来源

Codeforces 2149E，英文题名 Hidden Knowledge of the Ancients。