長さ n の 0 と 1 の列であって、000 -> 111 と 111 -> 000 を用いて 00000..... から作れるものを、実行可能解と呼び、1 の部分に対応する a _ i の合計をそのスコアと呼びます。まずは実行可能解の構造を見てみましょう。
実行可能解は次の 2 通りのいずれかです。（ただし両方に該当するケースもあります。）
- 区間全体を非空な 2 つの区間に分割し、左右実行可能解を合併した形
- 区間全体の長さが 3 の倍数であり、まず全体にスタンプを押したあと、ある真の部分区間における解を、0 と 1 を逆転して上書きした形
したがって、すべての区間についてそこにおける実行可能解のスコアの最大値、最小値を管理して、包含関係に関して昇順に計算していけばよいです。具体的には、貰う DP で区間 [l, r[ を見ているとして
- [l, r[ の非空な 2 つの区間への分割を全探索
- 左に 0 を追加、右に 0 を追加を試す
- 区間の長さが 3 の倍数ならば、反転を試す
を順に行えばよいです。3 つめの操作は、最小値を m、最大値を M として [ m, M ] = [ min ( m, sum - M ), max ( M, sum - m ) ] のようにするとよいです。（そもそも [ sum - m, M ] を管理すると累積和を使わなくても高速化できますが初期化がめんどくさいですし、そもそも高速化しなくても間に合います。）
提出：Submission #22331973 - AtCoder Grand Contest 050 (Good Bye rng_58 Day 1)
