题解

思路推导

可以证明，通过任意次追加后能够出现的最大值，等于原数组某个连续子数组的异或和最大值。令前缀异或为 $p_0=0$、$p_i=a_1\oplus\cdots\oplus a_i$，则子数组 $[l,r]$ 的异或和为 $p_r\oplus p_{l-1}$。

问题因此转化为：依次加入前缀异或值，求当前值与此前某个值异或后的最大值。

做法

维护一棵只包含 8 个二进制层级的 Trie，先插入 $p_0=0$。扫描数组并更新当前前缀异或 $p_i$。查询时从最高位到最低位，优先走与当前位相反的分支，从而使结果的当前位为 $1$；若该分支不存在再走相同位。用查询结果更新答案后，将 $p_i$ 插入 Trie。

正确性证明

任意子数组异或都可写成两个前缀异或之异或，反之任意两个前缀异或也唯一对应一个连续子数组。因此，只需在全部前缀异或值对中最大化异或结果。

处理 $p_i$ 时，Trie 恰包含 $p_0,\ldots,p_{i-1}$。二进制数大小由最高个不同位决定，所以查询在每一位优先选择相反分支，会在不影响更高位最优性的前提下最大化当前位；逐位贪心得到与 $p_i$ 异或最大的旧前缀。所有前缀依次查询后，全部值对都被考虑，最大值即为答案。

复杂度分析

每个前缀执行 8 层插入和查询，时间复杂度为 $O(8n)=O(n)$，空间复杂度为 $O(8n)$。