题目大意

给定一个长度为 $n$ 的非负整数序列 $a$，定义区间 $[l,r]$ 的权值为该区间内所有数的异或和。要求选出尽可能多的互不相交的区间，使得每个区间的异或和都等于给定的 $k$。求最多能选出多少个这样的区间。

---

核心思路：前缀异或 + 贪心

这是一道非常典型的前缀异或应用题，结合贪心思想即可解决。

1️⃣ 前缀异或的性质

定义前缀异或：

$$s_i = a_1 \oplus a_2 \oplus \dots \oplus a_i$$

特别地，令 $s_0 = 0$。

那么区间 $[l, r]$ 的异或和可以表示为：

$$a_l \oplus a_{l+1} \oplus \dots \oplus a_r = s_r \oplus s_{l-1}$$

因此，一个区间的异或和等于 $k$，等价于：

$$s_r \oplus s_{l-1} = k \quad \Longleftrightarrow \quad s_r = s_{l-1} \oplus k$$

---

2️⃣ 贪心策略：能选就选

由于区间不能相交，且目标是最大化区间数量，最自然的策略是：

从左到右扫描，一旦发现一个以当前位置结尾、异或和为 $k$ 的区间，就立即选中它，并从下一个位置重新开始。

这样做是正确的，因为：

• 选出一个区间后，它覆盖的位置就不再可用；
• 如果当前可以选而不选，后续不一定还能选出同样多的区间；
• 这种“尽早选取”的贪心在区间不相交问题中是通用且最优的。

---

3️⃣ 如何快速判断合法区间？

扫描到第 $i$ 个位置时，设当前前缀异或为 $s_i$。

根据上面的等价条件，只要之前出现过某个前缀异或值 $s_j$，满足：

$$s_j = s_i \oplus k$$

那么区间 $[j+1, i]$ 就是一个合法的、以 $i$ 结尾、异或和为 $k$ 的区间。

因此，我们只需要维护一个集合，记录在当前段中已经出现过的前缀异或值即可。

---

4️⃣ 算法流程

• 维护当前前缀异或值 pre；
• 用 map 记录在当前段中已出现的前缀异或值；
• 依次读入 $a_i$，更新 pre ^= a[i]；
• 判断是否存在合法区间：
  • 若 pre == k，说明从当前段起点到 $i$ 的整个区间异或和为 $k$；
  • 或若 pre ^ k 已在 map 中，说明存在某个 $j$ 使得 $[j+1, i]$ 满足条件；
• 一旦选中一个区间：
  • 答案加一；
  • 将 pre 重置为 0；
  • 清空 map，并重新插入 0（表示新段的起点）；
• 否则，将当前 pre 加入 map。

---

5️⃣ 为什么选中区间后要“清零 + 清空 map”？

这是本题的关键细节：

• 每选出一个区间 $[l, r]$，位置 $1 \sim r$ 都不可再使用；
• 下一个区间必须从 $r+1$ 开始；
• 而前缀异或是从序列开头计算的，但我们只关心“从新起点开始”的区间；
• 因此，将 pre 清零、重新建表，相当于把 $r+1$ 视为新的起点，逻辑完全自洽。

---

参考代码

#include <bits/stdc++.h>
using namespace std;
int n,k,x,pre,cn;
map<int,bool> m;
int main(){
    scanf("%d%d",&n,&k);
    m[0] = 1;
    for (int i = 1;i <= n;i++){
        scanf("%d",&x);
        pre ^= x;
        if (pre == k || m[pre ^ k]){
            pre = 0;
            cn++;
            m.clear();
            m[0] = 1;
        }else{
            m[pre] = 1;
        }
    }
    printf("%d",cn);
    return 0;
}

---

复杂度分析

• 时间复杂度：$O(n \log V)$，其中 $V$ 为异或值范围（map 操作带 $\log$）；
• 空间复杂度：$O(n)$，最坏情况下 map 存储所有前缀异或值。

若值域较小（如特殊性质 C），也可改用数组或 unordered_map 将复杂度优化至 $O(n)$。

---

样例解析

样例 1

4 2
2 1 0 3

• $s_1 = 2$，满足 pre == k，选取区间 $[1,1]$；
• 重置后继续扫描；
• $s_3 = 1 \oplus 0 \oplus 3 = 2$，再次满足 pre == k，选取区间 $[2,4]$；
• 答案为 2。

样例 3（$k = 0$）

4 0
2 1 0 3

• 只有在前缀异或为 0 时才能选取区间；
• 在 $i = 3$ 处，$s_3 = 2 \oplus 1 \oplus 0 = 0$，选取区间 $[3,3]$；
• 答案为 1。

---

总结

• 本题是前缀异或 + 贪心的经典模型；
• 核心等式：$s_r \oplus s_{l-1} = k$；
• 贪心原则：从左到右，能选就选；
• 每选一个区间，就“重新开始”一段，重置状态。

---

本题很好地考察了对异或性质的理解，以及将问题转化为前缀结构的能力，值得反复体会。

这是窝的洛谷号，请关注谢谢，看到必回关

临近CSP考试，祝所有看到这篇文章并关注我的人RP++！

RP++