← 返回题目列表

AtCoder · abc455_g

G. 平衡子数组

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

分数: 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.