分数: 625 点
问题陈述
给你一个序列 A of N 正整数。
其中 \frac{N(N+1)}{2} 的非空(连续)子数组 A,我们称之为序列 X 平衡序列当且仅当它满足以下条件:
- 中出现的每个整数 X 在中出现相同的次数 X.
对于每个 k=1,2,\dots,K,找到以下两个值:
- 每个整数准确出现的平衡序列的数量 B_k 次。
- 平衡序列的数量,其中恰好 出现 B_k 不同的整数。
如果两个子数组取自不同位置,则分别对它们进行计数 A,即使它们与序列相同。
解决 T 每个输入的测试用例。
约束
- 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.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
3 4 2 1 2 1 2 2 1 1 1 1 1 7 7 1 5 5 1 5 1 2 1 2 3 4 5 6 7
示例输出 1
1 4 7 4 1 1 13 8 3 8 1 1 0 0 0 0 0 0 0 0
对于第一个测试用例,对 (l,r) 这样的子数组 A 来自 l-th 通过 r-第一个元素是平衡序列 (1,1),(1,2),(1,4),(2,2),(2,3),(3,3),(3,4),(4,4),总共给出了八个实例。
其中,每个整数恰好出现两次的是 (1,4),给出一个实例,其中恰好出现两个不同整数的实例是 (1,2),(1,4),(2,3),(3,4),给出四个实例。
因此,对于 k=1,输出 1 4.
此外,每个整数只出现一次的是 (1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(4,4),给出七个实例,其中恰好出现一个不同整数的实例是 (1,1),(2,2),(3,3),(4,4),给出四个实例。
因此,对于 k=2,输出 7 4.