XOR 併合

$P_0=0$, $P_i=A_1\oplus A_2\oplus\cdots\oplus A_i$ とする。数列全体の XOR を $S=P_N$ とする。

分割操作は、$P$ の両端を変えずに内部へ任意の値を 1 個挿入する操作とみなせる。実際、$A_i$ を $x,y$ に分割すると、新しい prefix XOR $P_{i-1}\oplus x$ が と の間に入る。逆に、併合操作は内部の prefix XOR を 1 個削除する操作に対応する。

最終的な数列の長さが $m$ で、すべての要素が $k$ なら、prefix XOR は

$$0,k,0,k,\cdots$$

となる。また、全体 XOR $S$ はどちらの操作でも変化しない。

$S\ne 0$ の場合

$m$ は奇数であり、必ず $k=S$ である。したがって目標の prefix XOR は $0,S,0,S,\cdots,S$ である。

元の $P$ から値が $0$ または $S$ の要素だけを残す。この列を同じ値が連続する極大区間に分け、その個数を $C$ とする。各区間から 1 個だけ残せば $0,S,0,S,\cdots,S$ になる。その他の prefix XOR はすべて削除する必要があるため、答えは

$$N+1-C$$

である。

$S=0$ の場合

内部 prefix XOR $P_1,\cdots,P_{N-1}$ のうち、$0$ でないものの個数を $$ とする。また、prefix XOR 列全体で隣り合う と の間にできる区間数を とする。

$k=0$ を選ぶ場合、$0$ でない内部 prefix XOR をすべて削除すればよいので、コストは $M$ である。

次に $k\ne 0$ を固定する。すべての $0$ の prefix XOR を残しても最適値は悪化しない。連続する 2 個の $0$ の間には、目標列で $k$ がちょうど 1 個必要である。値 $k$ を少なくとも 1 回含む区間数を とする。そのような区間では を 1 個残して削除を 1 回減らせる。一方、 を含まない区間では を 1 個挿入する必要がある。よってコストは

$$M-H_k+(G-H_k)=M+G-2H_k$$

である。

$H=\max H_k$ とすれば、答えは

$$\min(M,\ M+G-2H)$$

となる。

$H$ は左から 1 回走査して求められる。prefix XOR が $0$ になるたびに区間番号を増やす。$0$ でない値 $v$ について、最後に数えた区間番号と、$v$ を含む異なる区間の個数をハッシュテーブルに保存する。同じ区間に $v$ が複数回現れても 1 回だけ数えることが重要である。

期待時間計算量は $O(N)$、メモリ計算量は $O(N)$ である。

Solution written by GPT5.6