异或为 K 的不相交区间

解题思路

先处理前缀异或：设P[i]=a1 XOR … XOR ai，则区间[l,r]异或为P[r] XOR P[l-1]。因此扫描到r时，只要允许的历史前缀里存在P[r] XOR K，就有一个合法区间以r结束。

接下来使用结束最早优先的区间贪心。一旦发现这样的区间，立即选入；后续仅允许从r+1开始选，清空旧前缀集合，只保留本次P[r]作为下一个区间之前的基准。这样不用枚举所有区间。

正确性说明

当前合法区间结束得最早。任一最优方案的第一个区间都不会早于它结束，将最优首区间替换为当前区间不会影响后面可选区间，所以至少存在同样优的方案以当前区间开头。对后缀重复交换论证，贪心选出的数量最多。集合只保留上个选中区间结束后可用的前缀，故所有选中区间两两不交。

易错点

K可以为0，区间仍必须非空：先查历史集合再插入当前前缀。每选中一段后必须清掉更早的前缀，避免跨过已选区间。

复杂度

使用set时O(N log N)时间，O(N)空间。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    cin >> N >> K;
    set<int> prefix;
    prefix.insert(0);
    int current = 0, answer = 0;
    for (int i = 1; i <= N; i++) {
        int x;
        cin >> x;
        current ^= x;
        if (prefix.count(current ^ K)) {
            answer++;
            prefix.clear();
            prefix.insert(current);
        } else
            prefix.insert(current);
    }
    cout << answer << "\n";
    return 0;
}