AT_abc455_g [ABC455G] Balanced Subarrays

给定一个长度为 $N$ 的正整数序列 $A$。 在 $A$ 所有 $\frac{N(N+1)}{2}$ 个非空（连续）子数组中，若某个子数组 $X$ 满足如下条件，我们称其为“平衡序列”： - $X$ 中出现的每个整数在 $X$ 中出现的次数都完全相同。 对于每一个 $k=1,2,\dots,K$，请分别求出以下两个值： - 使得每个整数在序列中恰好出现 $B_k$ 次的平衡序列个数。 - 恰好包含 $B_k$ 个不同整数的平衡序列个数。 若两个子数组取自 $A$ 的不同位置，即使它们作为序列完全相同，也应被视为不同。 对于每组输入，请求解 $T$ 组测试数据。

输入由标准输入给出，格式如下： > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 每组测试数据格式如下： > $N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_K$

输出格式如下： > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 对于每组测试数据，令 $c_{k,1}$ 表示每个整数恰好出现 $B_k$ 次的平衡序列个数，$c_{k,2}$ 表示恰好包含 $B_k$ 个不同整数的平衡序列个数，答案输出格式如下： > $c_{1,1}$ $c_{1,2}$ $c_{2,1}$ $c_{2,2}$ $\vdots$ $c_{K,1}$ $c_{K,2}$

### 样例解释 1 对于第一组测试数据，满足平衡序列定义的区间 $(l,r)$ 为 $(1,1),(1,2),(1,4),(2,2),(2,3),(3,3),(3,4),(4,4)$，共 $8$ 个。 其中，每个数都恰好出现两次的只有 $(1,4)$，共 $1$ 个；恰好有 $2$ 个不同数的有 $(1,2),(1,4),(2,3),(3,4)$，共 $4$ 个，因此 $k=1$ 时输出 `1 4`。 又，每个数恰好出现 $1$ 次的有 $(1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(4,4)$，共 $7$ 个；恰好有 $1$ 个不同数的有 $(1,1),(2,2),(3,3),(4,4)$，共 $4$ 个。因此 $k=2$ 时输出 `7 4`。 ### 数据范围 - $1\leq T\leq 2\times 10^5$ - $1\leq N\leq 2\times 10^5$ - $1\leq K\leq \min(N,10)$ - $1\leq A_i \leq N$ - $1\leq B_k \leq N$ - $B_1,B_2,\dots,B_K$ 互不相同。 - 所有测试数据中 $N$ 之和不超过 $2\times 10^5$。 - 所有输入数均为整数。 由 ChatGPT 5 翻译