まず、区間長 \(3\) に対する操作のみを考えるとして十分です。

固定された \(k\) に対する判定方法を考えます。 \(k\) 未満の数字を 0 に、\(k+1\) 以上の数字を 1 に置き換えた文字列 \(B\) を考えます。 また、整数 \(i\) は A[i] = k を満たすものとします。

01 列 \(S\) に対して、問題文中の操作を繰り返すことで達成可能な (0 の個数) \(-\) (1 の個数) の最小値と最大値をそれぞれ \(m(S), M(S)\) とします。 このとき、 \(A\) を長さ \(1\) の数列 \((k)\) にできる 必要十分条件は \(m[B[0,i)] + m[B[i+1,N)] \leq 0 \leq M[B[0,i)] + M[B[i+1,N)]\) です。

\(m(S)\) の効率的な求め方を述べます。 111 に対する操作は必要なく、000 に対する操作回数を最大化すべきです。特に、000 と 010 に対する操作を可能な限り繰り返すことで得られる文字列が \(m(S)\) を達成する文字列になります。\(M(S)\) についても同様です。

最後に、\(k=1, 2, \ldots, N\) に対する判定方法を説明します。 以上のアルゴリズムは segtree に乗せることができます。具体的には segtree の各ノードにおいて、その区間に対応する文字列の prefix, suffix 高々 \(3\) 文字を持てばよいです。以上より、 \(O(N\log{N})\) time でこの問題を解くことができます。