← 返回题目列表

Codeforces · 2151/A

A. 增量子数组

中文机器翻译题面 查看原题
Schtiffles - 大理石
⠀

詹姆斯正在学习数字,他很高兴将它们从左到右写在一块巨大的黑板上。

  • 开头,James 写下了数字 $$$1$$$。
  • 紧接着,James 又写了 $$$1$$$,然后是 $$$2$$$。
  • 然后 James 写入 $$$1$$$、$$$2$$$、$$$3$$$。
  • $$$\l点$$$
  • 最后,詹姆斯写了$$$1$$$、$$$2$$$、$$$3$$$、$$$\ldots$$$、$$$n$$$。

例如,对于 $$$n = 5$$$,James 写入的数字构成数组 $$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5]$$$。

James 有一个最喜欢的数字 $$$a_1, a_2, \ldots, a_m$$$ 的列表,他想计算数组 $$$b$$$ 有多少个子数组等于 $$$a_1, a_2, \ldots, a_m$$$。 $$$^{\text{*}}$$$

James 已经确定 $$$a_1, a_2, \ldots, a_m$$$ 是 $$$b$$$ 的子数组,所以答案至少是 $$$1$$$。

$$$^{\text{*}}$$$数组 $$$[v_1, v_2, \ldots, v_k]$$$ 的子数组生成如下:对于每个 $$$l, r$$$ 使得 $$$1 \leq l \leq r \leq k$$$,数组 $$$[v_l, v_{l+1}, \ldots, v_r]$$$ 是一个子数组。所以总共有 $$$k(k+1)/2$$$ 个子数组,并且其中一些可能是相等的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 200$$$) - James 写入的最大数字,以及数组 $$$a_1, a_2, \ldots, a_m$$$ 的长度。

每个测试用例的第二行包含 $$$m$$$ 整数 $$$a_1, a_2, \ldots, a_m$$$ ($$$1 \leq a_i \leq 10^5$$$) - James 最喜欢的数字。

保证对于给定的输入,答案始终至少为 $$$1$$$。

请注意,所有测试用例的 $$$n$$$ 和 $$$m$$$ 之和没有限制。

输出

对于每个测试用例,输出一行包含一个整数:数组 $$$b$$$ 中等于 $$$a_1, a_2, \ldots, a_m$$$ 的子数组的数量。

示例

输入
复制

5
4 1
1
5 3
1 2 3
6 6
3 1 2 3 4 1
100000 1
100000
4 2
1 1

输出
复制

4
3
1
1
1

注意

在第一个测试用例中,黑板上包含数字

$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4]$$

而詹姆斯只有一个最喜欢的号码:号码$$$1$$$。 $$$b$$$ 有 $$$4$$$ 子数组等于 $$$[1]$$$(以红色突出显示):

  • $$$[\color{红色}{1}, 1, 2, 1, 2, 3, 1, 2, 3, 4]$$$;
  • $$$[1, \color{红色}{1}, 2, 1, 2, 3, 1, 2, 3, 4]$$$;
  • $$$[1, 1, 2, \color{红色}{1}, 2, 3, 1, 2, 3, 4]$$$;
  • $$$[1, 1, 2, 1, 2, 3, \color{红色}{1}, 2, 3, 4]$$$。

在第二个测试用例中,黑板上包含数字

$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5]$$

詹姆斯最喜欢的数字列表是 $$$[1, 2, 3]$$$。 $$$b$$$ 有 $$$3$$$ 子数组等于 $$$[1, 2, 3]$$$(以红色突出显示):

  • $$$[1, 1, 2, \color{红色}{1, 2, 3}, 1, 2, 3, 4, 1, 2, 3, 4, 5]$$$;
  • $$$[1, 1, 2, 1, 2, 3, \color{红色}{1, 2, 3}, 4, 1, 2, 3, 4, 5]$$$;
  • $$$[1, 1, 2, 1, 2, 3, 1, 2, 3, 4, \color{红色}{1, 2, 3}, 4, 5]$$$。

在第三个测试用例中,黑板上包含数字

$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6]$$

詹姆斯最喜欢的号码是 $$$[3, 1, 2, 3, 4, 1]$$$。 $$$b$$$ 中只有 $$$1$$$ 子数组等于 $$$[3, 1, 2, 3, 4, 1]$$$(以红色突出显示):

  • $$$[1, 1, 2, 1, 2, \color{红色}{3, 1, 2, 3, 4, 1}, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6]$$$。