数列 \((0,0)\) に対して操作を何回か行うことで得られる長さ \(2\) 以上の数列 \(C\) の条件は

• \(1\) が含まれない

数列 \((0,1)\) に対して操作を何回か行うことで得られる長さ \(2\) 以上の数列 \(C\) の条件は

• \(C_1=0, \; C_{|C|}=1\)
• \(0\) が連続しない

数列 \((1,1)\) に対して操作を何回か行うことで得られる長さ \(2\) 以上の数列 \(C\) の条件は

• \(C_1=1, \; C_{|C|}=1\)
• \(2 < |C|\) ならば \(0\) を含む
• \(0\) が連続しない

となります。 数列 \(A\) のうち、\(|B|\) が最小となるような \(B\) に含まれる要素について考えます。

\(A_1\) と \(A_N\) は \(B\) に含まれます。

• \(l<r\)
• \(A_l=A_{l+1}=\dots=A_{r}=0\)
• \(l=1\) または \(A_{l-1}=1\)
• \(r=N\) または \(A_{r+1}=1\)

を満たす \(l,r\) に対し、\(A_l\) と \(A_r\) は \(B\) に含まれ、\(A_{l+1},A_{l+2},\dots,A_{r-1}\) は \(B\) に含める必要はないことがわかります。 また、このような \(l,r\) に対して \(A_l,A_{l+1},\dots,A_r\) を削除してその部分で区切った時、区切られた連続部分列は \(1\) を \(1\) つ以上含んでいてそのうちの \(1\) つは \(B\) に含まれる必要があり、またそれで十分なこともわかるため、この区切りの個数で \(|B|\) の最小値を求めることができます。
\((A_1,A_2)=(0,1)\) や \((A_N,A_{N-1})=(0,1)\) の場合には同じ連続部分列から \(2\) つの要素を \(B\) に含める必要があることに注意してください。

変更クエリごとにこの値を求めるためには、削除する（\(0\) が \(2\) つ以上続く）連続部分列が何個あるかを管理すればよく、計算量は全体で \(O(N+Q)\) です。