次のクエリを高速に処理できることは有名です。

はじめ、\(a = (a_0, a_1, \dots, a_{n-1})\) が与えられているとします。

• \(\texttt{1}\; i\; x\)
  • \(a_i \gets x\) で更新する
• \(\texttt{2}\; l\; r\)
  • \(\max_{l\le i_l\lt i_r\le r} \sum_{j=i_l}^{i_r-1} a_j\) を出力する

2 番目のクエリは、直感的に言えば、\([l\,.\,.\,r)\) の範囲における区間和の最大値を求めるものです。

ABC 175 D (bonus) ユーザ解説 と似たモノイドを考え、セグ木を用いることで可能です。

さて、今回の問題は次のようにして上記のクエリ問題に帰着できます。0-indexed として適切に変換して考えるものとします。

長さ \(2N-1\) の列 \(a = (a_0, a_1, \dots, a_{2(N-1)})\) を次のように定義します。 まず、\(i\) 文字目 (\(0\le i\lt N\)) には \(a_{2i}\) が対応するものとし、常に \(a_{2i} = 1\) とします。 次に、\(i\) 文字目と \(i+1\) 文字目の境界 (\(0\le i\lt N-1\)) には \(a_{2i+1}\) が対応するものとし、\(S_i = S_{i+1}\) のときは \(a_{2i+1} = 0\)、そうでないときは \(a_{2i+1} = -\infty\) とします。

たとえば、\(S = \texttt{bbaaabb}\) のとき、

\[ a = (1, 0, 1, -\infty, 1, 0, 1, 0, 1, -\infty, 1, 0, 1) \]

となります。

更新の際は両側の境界を適切に更新し、\(f(t)\) を求める際は \([2l\,.\,.\,2r]\) の範囲について区間和の最大値を求めればよいです。

note: 異なる文字が存在するときの \(1\) の最大連続数などを考えると、\(-\infty\) の代わりに \(-N\) などを使っても問題ないことがわかります。