AT_abc455_g [ABC455G] Balanced Subarrays

長さ $ N $ の正整数列 $ A $ が与えられます。 $ A $ の空でない連続部分列は $ \frac{N(N+1)}{2} $ 個ありますが、そのうち以下の条件を満たす数列 $ X $ をバランスの良い数列と呼ぶことにします。 - $ X $ に含まれる各整数は $ X $ 内に同じ回数登場する $ k=1,2,\dots,K $ について、以下の $ 2 $ 種類の値をそれぞれ求めてください。 - バランスの良い数列のうち、各整数が $ B_k $ 回ずつ登場するものの個数 - バランスの良い数列のうち、 $ B_k $ 種類の整数が登場するものの個数 ただし、 $ 2 $ つの連続部分列は、 $ A $ から取り出す場所が異なれば数列として同じでも区別して数えることに注意してください。 $ 1 $ つの入力につき、 $ 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 $ 各ケースでは、バランスの良い数列のうち、各整数が $ B_k $ 回ずつ登場するものの個数を $ c_{k,1} $ 、 $ B_k $ 種類の整数が登場するものの個数を $ c_{k,2} $ として、以下の形式で出力せよ。 > $ c_{1,1} $ $ c_{1,2} $ $ c_{2,1} $ $ c_{2,2} $ $ \vdots $ $ c_{K,1} $ $ c_{K,2} $

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、 $ A $ の $ l $ 番目から $ r $ 番目までの連続部分列がバランスの良い数列であるような $ (l,r) $ の組は $ (1,1),(1,2),(1,4),(2,2),(2,3),(3,3),(3,4),(4,4) $ の $ 8 $ つです。 そのうち、各整数が $ 2 $ 回ずつ登場するのは $ (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` を出力してください。 ### Constraints - $ 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 $ 以下 - 入力される値は全て整数