CF2151A.Incremental Subarray

Schtiffles - Marbl

⠀

James 正在学习数字，并且他很开心地从左到右地把数字写在一块巨大的黑板上。

• 一开始，James 写下数字 $1$。
• 接着，James 再次写下 $1$，然后写下 $2$。
• 然后 James 写下 $1$、$2$、$3$。
• $ \ldots $
• 最后，James 依次写下 $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$ 完全相同。$^{\ast}$

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

$^{\ast}$ 数组 $[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 \leq t \leq 500$），表示测试用例数量。每组测试用例的描述如下：

每组测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^5$，$1 \leq m \leq 200$）——James 要写的最大数字 $n$ 以及数组 $a_1, \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$ 的子数组数量。

在第一个测试用例中，黑板上的数字为

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

James 只有一个喜欢的数字：$1$。$b$ 中有 $4$ 个子数组等于 $[1]$（用红色标记）：

• $[\red{1}, 1, 2, 1, 2, 3, 1, 2, 3, 4]$；
• $[1, \red{1}, 2, 1, 2, 3, 1, 2, 3, 4]$；
• $[1, 1, 2, \red{1}, 2, 3, 1, 2, 3, 4]$；
• $[1, 1, 2, 1, 2, 3, \red{1}, 2, 3, 4]$。

在第二个测试用例中，黑板上的数字为

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

James 的喜欢数字列表是 $[1, 2, 3]$。$b$ 中有 $3$ 个子数组等于 $[1, 2, 3]$（用红色标记）：

• $[1, 1, 2, \red{1, 2, 3}, 1, 2, 3, 4, 1, 2, 3, 4, 5]$；
• $[1, 1, 2, 1, 2, 3, \red{1, 2, 3}, 4, 1, 2, 3, 4, 5]$；
• $[1, 1, 2, 1, 2, 3, 1, 2, 3, 4, \red{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]$$

James 的喜欢数字列表是 $[3, 1, 2, 3, 4, 1]$。$b$ 中只有 $1$ 个子数组等于 $[3, 1, 2, 3, 4, 1]$（用红色标记）：

• $[1, 1, 2, 1, 2, \red{3, 1, 2, 3, 4, 1}, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6]$。

由 ChatGPT 5 翻译