M - Swapping Brackets Editorial by Nachia

より高速な解法

計算量オーダー \(O(|S|)\) の解法があるということの紹介です。

公式解説 において、 BIT を使わず、素朴な配列と今見ている \(f(l,s)\) の値のみ管理することを考えます。

一様加算はできませんが、代わりに要素の個数の計算を \(f(l,s)\) の計算と同時に行います。

提供すべき操作に \(l\) のインクリメント、 \(s\) のインクリメント、必要な総和の取得がありますが、それぞれ計算量 \(O(1)\) で処理できます。

よって、全体の計算量を \(O(|S|)\) にできました。

解答例

posted:
last update: