文字列 \(S_{1},S_{2}\) に対して、

• 左側から \(0\) が連続している数
• 右側から \(0\) が連続している数
• \(0\) が連結している数の最大値
• 文字列自体の長さ

がわかっているとき、 \(S_{1}+S_{2}\) に対する上記の値を \(O(1)\) で求めることができます。

よって、一番最初に与えられる文字列を長さ \(N\) のセグメントツリーにのせることで、 任意の \(i\) に対する \(S_{i}\) の上記の値を \(O(\log(N))\) で求めることができます。

undo がなければ Union Find Tree で解けます。

undo があっても undo 付き Union Find Tree で解けます。

公式の解説 (トップページにあります) では永続データ構造を使っていますが、その必要はないです。

最初にクエリを全て受け取り、操作列の木を作ったあと DFS すれば良いです。

答えが int 型に収まらないことがあることに注意してください。

実装例 https://atcoder.jp/contests/tkppc/submissions/45990382