M - Swapping Brackets Editorial by Nachia
より高速な解法計算量オーダー \(O(|S|)\) の解法があるということの紹介です。
公式解説 において、 BIT を使わず、素朴な配列と今見ている \(f(l,s)\) の値のみ管理することを考えます。
一様加算はできませんが、代わりに要素の個数の計算を \(f(l,s)\) の計算と同時に行います。
提供すべき操作に \(l\) のインクリメント、 \(s\) のインクリメント、必要な総和の取得がありますが、それぞれ計算量 \(O(1)\) で処理できます。
よって、全体の計算量を \(O(|S|)\) にできました。
posted:
last update: