XOR 合并

令 $P_0=0$，$P_i=A_1\oplus A_2\oplus\cdots\oplus A_i$。记整个序列的 XOR 为 $S=P_N$。

分割操作等价于在保持 $P$ 两个端点不变的情况下，在内部插入一个任意值。把 $A_i$ 分割为 $x,y$ 时，新插入的前缀 XOR 为 $P_{i-1}\oplus x$。反过来，合并操作恰好删除一个内部前缀 XOR 。

如果最终序列长度为 $m$，且所有元素都等于 $k$，那么它的前缀 XOR 序列为

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

两种操作都不会改变总 XOR $S$。

$S\ne 0$ 的情况

此时 $m$ 必须为奇数，并且必有 $k=S$。目标前缀 XOR 序列为 $0,S,0,S,\cdots,S$。

从原来的 $P$ 中只保留值为 $0$ 或 $S$ 的元素。把得到的序列划分为若干个值相同的极大连续段，设段数为 $C$。每段只保留一个元素，就会得到 $0,S,0,S,\cdots,S$。其余前缀元素都必须删除，因此答案为

$$N+1-C.$$

$S=0$ 的情况

设内部前缀 XOR $P_1,\cdots,P_{N-1}$ 中非零元素的个数为 $M$。设完整前缀序列中相邻两个零之间的区间数为 $$。

若选择 $k=0$，删除所有非零内部前缀即可，代价为 $M$。

现在固定 $k\ne 0$。保留所有值为 $0$ 的前缀不会使最优解变差。每两个相邻的零之间，在目标序列中恰好需要一个 $k$。设至少包含一次值 $k$ 的区间数为 $H_k$。在这些区间中可以保留一个 ，少删除一次；在不含 的区间中则需要插入一个 。因此代价为

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

令 $H=\max H_k$，最终答案为

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

可以通过一次从左到右的扫描求出 $H$。每遇到一个值为 $0$ 的前缀就增加区间编号。对于每个非零值 $v$，在哈希表中记录它上一次被计数的区间编号，以及包含 $v$ 的不同区间数量。这样同一区间内多次出现的 $v$ 只会被计数一次。

期望时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。

Solution written by GPT5.6