题解：P14359 [CSP-J 2025] 异或和 / xor（民间数据）

herezz · 2025-11-01 14:59:03 · 题解

题意： 给定一个长度为 n 的序列 a 和 k，尝试选择尽可能多的不相交的区间，使每个区间的异或和都为 k。

思路： 由于 a\oplus b\oplus b=a，考虑使用类似前缀和的做法来求区间异或和，并用 map 存可以使区间 [1,i] 的异或和为 x 的所有 i。因为区间不相交，所以考虑维护最后一个区间的尾部，从 1 到 n 枚举 i，upper_bound 一下不小于最后一个区间的结尾，小于 i，且 [j,i] 的异或和为 k（即 [1,j] 的异或和 \oplus [1,i] 的异或和）的最小的 j（可以证明，选哪个 j 不影响答案），如果找到了，答案加 1，更新最后一个区间的末尾。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[500010],s[500010],vis=-1,ans,n,k;//vis初始化为-1，因为s[0]也可以用
map<int,vector<int>>mp;
int main(){
    cin>>n>>k;
    mp[0].push_back(0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]^a[i];
        mp[s[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        auto pl=upper_bound(mp[s[i]^k].begin(),mp[s[i]^k].end(),vis);//求大于vis（即不小于最后一个区间的结尾）的最小j
        if(pl==mp[s[i]^k].end())continue;//防止访问空地址导致RE
        if(*pl<i)ans++,vis=i-1;
    }
    cout<<ans<<endl;
}