← 返回题目列表

Codeforces · 1955/D

D. 子序列搜索不准确

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

Maxim 有一个包含 $$$n$$$ 整数的数组 $$$a$$$ 和一个包含 $$$m$$$ 整数的数组 $$$b$$$ ($$$m \le n$$$)。

Maxim 认为,如果数组 $$$c$$$ 的元素可以重新排列,使得至少 $$$k$$$ 与数组 $$$b$$$ 的元素匹配,则 Maxim 认为长度为 $$$m$$$ 的数组 $$$c$$$ 是好的。

例如,如果 $$$b = [1, 2, 3, 4]$$$ 和 $$$k = 3$$$,则数组 $$$[4, 1, 2, 3]$$$ 和 $$$[2, 3, 4, 5]$$$ 就很好(它们可以按如下方式重新排序:$$$[1, 2, 3, 4]$$$ 和 $$$[5, 2, 3, 4]$$$),而数组 $$$[3, 4, 5, 6]$$$ 和 $$$[3, 4, 3, 4]$$$ 则不好。

Maxim 希望选择数组 $$$a$$$ 长度为 $$$m$$$ 的每个子段作为数组 $$$c$$$ 的元素。帮助 Maxim 计算有多少个选定的阵列是好的。

换句话说,找到位置的数量 $$$1 \le l \le n - m + 1$$$ 使得元素 $$$a_l, a_{l+1}, \dots, a_{l + m - 1}$$$ 形成一个好的数组。

输入

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

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le k \le m \le n \le 2 \cdot 10^5$$$) - 数组 $$$a$$$ 和 $$$b$$$ 中的元素数量,即所需的匹配元素数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — 数组 $$$a$$$ 的元素。数组 $$$a$$$ 的元素不一定是唯一的。

每个测试用例的第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^6$$$) — 数组 $$$b$$$ 的元素。数组 $$$b$$$ 的元素不一定是唯一的。

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

输出

对于每个测试用例,在单独的行上输出数组 $$$a$$$ 的良好子段的数量。

示例

输入 #1

5
7 4 2
4 1 2 3 4 5 6
1 2 3 4
7 4 3
4 1 2 3 4 5 6
1 2 3 4
7 4 4
4 1 2 3 4 5 6
1 2 3 4
11 5 3
9 9 2 2 10 9 7 6 3 6 3
6 9 7 8 10
4 1 1
4 1 5 6
6

输出 #1

4
3
2
4
1

注意

在第一个示例中,所有子段都很好。

在第二个示例中,好的子分段从位置 $$$1$$$、$$$2$$$ 和 $$$3$$$ 开始。

在第三个示例中,好的子分段从位置 $$$1$$$ 和 $$$2$$$ 开始。