异或和 (CSP-J 2025)

第三题开始有一些难度，需要思考一下。题目要求我们计算一个 $n$ 长序列中（ $n\leq 5\cdot 10^5$ ），XOR为 $k$ ，而且互相没有重叠的子序列的最大数量。

区间的XOR，比较容易想到用前缀和，或者说前缀XOR。虽然可能不容易看出来和“最大区间数”有什么关系，但前缀XOR可以帮助我们 $\mathcal{O}(1)$ 计算任何一个区间的XOR：

$a[i] \oplus a[i+1] \oplus \cdots \oplus a[j] = prefix\_xor[i-1] \oplus prefix\_xor[j]$

对于一个固定的区间尾 $j$ 来说，就可以有多个 $i$ 使得 $[i,j]$ 区间的XOR是 $k$ 。这时我们观察到：由于我们需要计算“最大区间数”，对于一个固定的区间尾 $j$ ，我们应该贪心地选择最大的 $i$ ，使得 $[i,j]$ 区间的XOR是 $k$ 。这个比较容易理解： $i$ 越大，区间越短，能够允许的区间数越多（在区间尾 $j$ 不变的情况下）。

所以基于这一贪心思路，我们可以计算如下 $b[j]$ ：对每个 $j$ ，可以计算最大的 $b[j]$ ，使得 $[b[j]+1,j]$ 的XOR为 $k$ 。这个就用前缀xor + unordered_map来计算就可以了，即定义 $m[x]$ ，记录 $1..j$ 中，前缀XOR为 $x$ 的最后一个位置。

有了 $b[j]$ 之后，我们就可以使用一个类似背包的DP来计算最终的结果：定义 $dp[i]$ 为 $i$ 为结尾的子序列中不重叠的XOR为 $k$ 的子序列个数的最大值。则有：

$dp[i] = \max(dp[i-1], dp[b[i]] + 1)$

最终结果就是 $ans = dp[n]$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, k;
int a[500005], b[500005];
int pxor[500005];
int dp[500005];
unordered_map<int,int> m;
 
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pxor[i] = pxor[i-1] ^ a[i];     // compute prefix xor
        int d = pxor[i] ^ k;            // compute expected prefix xor
        if (m.find(d) != m.end())       // find prefix xor
            b[i] = m[d];
        else if (d == 0)                // special case: prefix xor is 0
            b[i] = 0;                   // use the whole sequence
        else                            // not found
            b[i] = -1;
        m[pxor[i]] = i;                 // update the last position of the prefix xor
    }
 
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i-1];
        if (b[i] >= 0)
            dp[i] = max(dp[i], dp[b[i]] + 1);
    }
 
    printf("%d\n", dp[n]);
    return 0;
}