J - AB Sort 解説
by
potato167
公式解説(トップページにある)に夜とセグメントツリーで解けると書いてありましたがわかりませんでした。
代わりに遅延セグメントツリーで解く方法を記します。
まず、\(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}\) について上記の値も定数時間でわかります。
遅延セグメントツリーでのる形であるため、これで求まります。