XOR Merge

Let $P_0=0$ and $P_i=A_1\oplus A_2\oplus\cdots\oplus A_i$. Let $S=P_N$ be the XOR of the whole sequence.

A split operation is exactly the insertion of one arbitrary internal value into $P$ while keeping both endpoints fixed. If $A_i$ is split into $x,y$, the newly inserted prefix value is $P_{i-1}\oplus x$. Conversely, a merge operation deletes exactly one internal prefix value .

If the final sequence has length $m$ and every element is $k$, its prefix XOR sequence is

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

The total XOR $S$ is invariant under both operations.

Case $S\ne 0$

Then $m$ must be odd and $k=S$. The target prefix sequence is $0,S,0,S,\cdots,S$.

Filter the original $P$ so that only values equal to $0$ or $S$ remain. Let $C$ be the number of maximal runs of equal values in this filtered sequence. Keeping one value from every run gives exactly an alternating sequence $0,S,0,S,\cdots,S$. Every other prefix value must be deleted, so the answer is

$$N+1-C.$$

Case $S=0$

Let $M$ be the number of nonzero values among the internal prefixes $P_1,\cdots,P_{N-1}$. Let be the number of gaps between consecutive zero values in the full prefix sequence.

For $k=0$, deleting every nonzero internal prefix is sufficient, so the cost is $M$.

Now fix $k\ne 0$. Keeping every zero prefix never makes an optimum worse. Each gap between two consecutive zeros needs exactly one $k$ in the target. Let $H_k$ be the number of gaps that already contain at least one prefix equal to . In such a gap we can keep one occurrence of and save one deletion. In every other gap we must insert one . Therefore the cost is

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

If $H=\max H_k$, the answer is

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

We can compute $H$ in one scan. Increase the gap index whenever the current prefix is zero. For every nonzero value $v$, store in a hash table the last gap in which $v$ was counted and the number of distinct gaps containing $v$. This makes repeated occurrences of $v$ inside the same gap count only once.

The expected time complexity is $O(N)$ and the memory complexity is $O(N)$.

Solution written by GPT5.6