公式解説(トップページにある)に夜とセグメントツリーで解けると書いてありましたがわかりませんでした。

代わりに遅延セグメントツリーで解く方法を記します。

まず、\(f(t)\) は \(t\) の最初の文字が B であるとき以下のようになります。

\(g(t,i)\) を [\(t_{k}\) が B であるような \(i\) 未満の \(k\) の数] \(+\) [\(t_{k}\) が A であるような \(i\) より大きい \(k\) の数] とします。

\(t_{i}\) が A であるような \(i\) のうち、\(g(t,i)\) の最大値

以下、 \(f(t)\) は上の定義に置き換えます。

\(S_{1},S_{2}\) について、以下の値がわかっているとします。

• \(S\) に含まれる A の数
• \(S\) に含まれる B の数
• \(f(S)\)
• \(S\) を反転したときの \(f(S)\)

このとき、 \(S_{1}+S_{2}\) について上記の値も定数時間でわかります。

遅延セグメントツリーでのる形であるため、これで求まります。

実装例 c++