MEXOR

$P(l,r)$ を、$A_l,\ldots,A_r$ に含まれる $0$ の個数の偶奇とします。すべての要素を長さ $1$ の区間に分けた場合の XOR 値は $P(1,N)$ です。

区間 $[l,r]$ 内の単独区間を一つの区間に置き換えると、XOR 値の変化量は $\mathrm{MEX}(l,r)\oplus P(l,r)$ です。したがって、互いに重ならない区間を選び、それぞれの変化量を XOR する問題として考えられます。

MEX が $0$ の区間の変化量は $0$ です。MEX が $1$ の区間には $1$ が含まれません。$0$ が奇数個なら変化量は $0$ であり、偶数個なら、その区間内にある連続する二つの $0$ の位置の間の、 を含まない区間に置き換えられます。この短い区間の変化量は です。

次に MEX が $m\ge2$ の区間を考えます。その内部から $0,1,\ldots,m-1$ をすべて含む最短の部分区間 $[u,v]$ を選びます。両端の値は 未満で、部分区間内にそれぞれちょうど一度だけ現れます。このような区間を と呼びます。左端を固定して出現回数と MEX を更新することで列挙できます。

除去した部分に含まれる $0$ が偶数個なら、本質的な区間だけで同じ変化量を得られます。奇数個なら、元の区間内で本質的な区間の左側または右側にある最も近い $0$ まで拡張します。これで $0$ がちょうど一つ増え、元の区間に $m$ が存在しないため MEX は変わりません。よって、本質的な区間と、MEX を変えない左右いずれか一方への拡張だけを候補にすれば十分です。候補の総数は $O(N)$ 個です。

$dp[i]$ を、接頭区間 $[1,i]$ 内で互いに重ならない候補を選んで得られる変化量の XOR 値の集合とします。位置 $i$ を使わない場合と、右端が $i$ の候補 $[l,i]$ を選び、 の各値にその変化量を XOR する場合を遷移させます。

列全体の MEX を $G$ とすると、任意の区間の MEX は $G$ 以下です。XOR 値は $2^{\lceil\log_2(G+1)\rceil}$ 未満なので、ビット集合を用いた DP により時間計算量 、空間計算量 で解けます。答えは に対する の最大値です。