(Unkind) Sandwich Degree

不親切ポイント

(プラットフォーム別のフォーマットを優先したうえで)よいこはマネしないで

• 明らかに無駄な描写
• $3\times 10^6$
• サンプルが弱い
• 入力欄が Codeforces （Codeforces が悪いのではなく、コンテスト内で揃えないのがよくない）
• 十分な効果がない「引用」を用いた問題文 markdown

想定解法

• 文字列 $X$ の $a$ 番目から $b$ 番目の文字を取り出した部分文字列を $X_{[a,b]}$ で表します。 $a \gt b$ のとき、 $X_{[a,b]}$ は空文字列とします。
• 計算量の表示では、文字の種類数を $C$ とします。

文字種ごとに分解して考えます。 A に注目するとします。

突然ですが、文字列 $X$ について以下の値を求めておいたとします。 $\cdots \cdots (1)$

• $\mathrm{C_{nt}}(X)$ : A の数
• $\mathrm{S_{idx}}(X)$ : A のインデックス(0-based)の総和
• $\mathrm{S_{len}}(X)$ : 嬉しさ 、ただし $X[i]=X[j]=$ A の場合のみ考える。

すると、 $X,X+Y$ の場合の $(1)$ の結果から $\mathrm{S_{len}}(Y)$ が計算できます。

• $\mathrm{C_{nt}}(Y) = \mathrm{C_{nt}}(X+Y) - \mathrm{C_{nt}}(X)$
• $\mathrm{S_{idx}}(Y) = \mathrm{S_{idx}}(X+Y) - \mathrm{S_{idx}}(X)$
• $\mathrm{S_{len}}(Y) = \mathrm{S_{len}}(X+Y) - \mathrm{S_{len}}(X) - \mathrm{C_{nt}}(Y) \times \mathrm{S_{idx}}(X) + \mathrm{C_{nt}}(X) \times (\mathrm{S_{idx}}(Y) + \mathrm{C_{nt}}(Y))$

したがって、クエリ $(l,r)$ に関して、 $S_{[1,l-1]}$ と $S_{[1,r]}$ について $(1)$ の結果がわかっていれば、このクエリに $O(1)$ 時間で答えられます。

$S$ の長さに対してクエリ数が小さいので、座標圧縮をします。その結果をもとに $S_{[1,l-1]},S_{[1,r]}$ を列挙することは、累積和のようにして $O(N+QC+Q \log Q)$ 時間で可能です。

全体の計算量は $O(N+QC+Q \log Q)$ です。空間計算量は $O(N+QC)$ です。

クエリの答えとしてありうる値は最大で $4500009000002500000 \fallingdotseq 4.5 \times 10^{18}$ です。オーバーフローに注意してください。