問題原案：admin

累積和

次の問題を考えます。

問題：「\(S\) の \(l\) 文字目から \(r\) 文字目までに \(a\) は何個含まれるか」というクエリがたくさん与えられるので答えよ。

\(S\) の \(i\) 文字目までに含まれる \(a\) の個数を \(X_i\) とします。以下のようにして、\(i\) の昇順に計算することで \(X_0,\ldots,X_N\) を \(O(N)\) 時間で求めることができます。
\(X_i=\begin{cases} 0 & i=0\\ X_{i-1} & S_i\neq a\\ X_{i-1}+1 & S_i=a \end{cases}\)

この \(X\) を用いることで、\(S\) の \(l\) 文字目から \(r\) 文字目までに含まれる \(a\) の個数は \(X_r-X_{l-1}\) と \(O(1)\) で求めることができます。

二分探索

予め累積和を求めておくことで、各区間に含まれるa , b の個数は \(O(1)\) で取得できるとしてよいです。

\(l\) を固定したとき条件を満たす \(r\) が何個あるかを考えます。

• \(r\) が大きくなればなるほど \([l,r]\)に含まれる a の個数は増えます。よって \(a_l\) を「\([l,r]\) に含まれる a の個数が \(A\) 個以上となる最小の \(r\) 」と定めると、a の個数に関する条件は \(r \geq a_l\) と同値
• \(r\) が大きくなればなるほど \([l,r]\)に含まれる b の個数は増えます。よって \(b_l\) を「\([l,r]\) に含まれる b の個数が \(B\) 個未満となる最大の \(r\) 」と定めると、b の個数に関する条件は \(r\leq b_l\) と同値

\(a_l,b_l\) は二分探索により \(O(\log N)\) 時間で求めることができ、条件を満たす \(r\) の個数は \(\max(0,b_l-a_l+1)\) となります。（実装上は「\([l,r]\) に含まれる a の個数が \(A\) 個以上となる最小の \(r\) 」が存在しないケースなどに注意してください）

全ての \(l\) についてこれを行うことで全体で \(O(N\log N)\) 時間でこの問題を解くことができます。

さらに、ここで定めた \(a_l, b_l\) はそれぞれ \(l\) について単調増加なので、尺取法を用いて全体で \(O(N)\) 時間でこの問題を解くこともできます。