解説

それぞれの $k$ について、 $C_k S_k$ を高速に求める方法を考えます。

まず、 $S_k$ は累積和によって前処理 $O(N)$ 、クエリ $O(1)$ で求まります。

次に、 $C_k$ について考えると、これは Z-algorithm を工夫して使うことで求まります。 数列 $X$ に対して、 $X$ を逆順に並べたものを $X^R$ と表記することにします。

数列 $T$ を、 $A^R$ 、 $-1$ 、 $B^R$ の順で並べたものと定義します。 例えば、 $A = (1, 2, 3), B = (4, 5, 6)$ のとき、 $C = (3, 2, 1, -1, 6, 5, 4)$ となります。

数列 $Z$ を、 $Z_i =$ 数列 $C$ の前から $i$ 文字目までの接尾辞と $C$ の最長共通接頭辞の長さと定義します。 数列 $Z$ は Z-algorithm を使って $O(N + M)$ で求めることができます。 このとき、 $C_k$ は数列 $Z$ の $N+1$ 番目以降にある $k$ 以上の値の数です。