A17434. T3 异或和异或和（xor）
题目描述
T3 异或和
异或和（xor）
题目描述
小 R 有一个长度为 n 的非负整数序列 a1,a2,…,an。定义一个区间 [l,r]（1≤l≤r≤n）的权值为 al,al+1,…,ar 的二进制按位异或和，即 al⊕al+1⊕⋯⊕ar，其中 ⊕ 表示二进制按位异或。
小 X 给了小 R 一个非负整数 k。小 X 希望小 R 选择序列中尽可能多的不相交的区间，使得每个区间的权值均为 k。两个区间 [l1,r1],[l2,r2] 相交当且仅当两个区间同时包含至少一个相同的下标，即存在 1≤i≤n 使得 l1≤i≤r1 且 l2≤i≤r2。
例如，对于序列 [2,1,0,3]，若 k=2，则小 R 可以选择区间 [1,1] 和区间 [2,4]，权值分别为 2 和 1⊕0⊕3=2；若 k=3，则小 R 可以选择区间 [1,2] 和区间 [4,4]，权值分别为 1⊕2=3 和 3。
你需要帮助小 R 求出他能选出的区间数量的最大值。
输入格式
从文件 xor.in 中读入数据。
输入的第一行包含两个非负整数 n,k，分别表示小 R 的序列长度和小 X 给小 R 的非负整数。
输入的第二行包含 n 个非负整数 a1,a2,…,an，表示小 R 的序列。
输出格式
输出到文件 xor.out 中。
输出一行一个非负整数，表示小 R 能选出的区间数量的最大值。
样例 1 输入
4 2
2 1 0 3样例 1 输出
2样例 1 解释
小 R 可以选择区间 [1,1] 和区间 [2,4]，异或和分别为 2 和 1⊕0⊕3=2。可以证明，小 R 能选出的区间数量的最大值为 2。
样例 2 输入
4 3
2 1 0 3样例 2 输出
2样例 2 解释
小 R 可以选择区间 [1,2] 和区间 [4,4]，异或和分别为 1⊕2=3 和 3。可以证明，小 R 能选出的区间数量的最大值为 2。
样例 3 输入
4 0
2 1 0 3样例 3 输出
1样例 3 解释
小 R 可以选择区间 [3,3]，异或和为 0。可以证明，小 R 能选出的区间数量的最大值为 1。注意：小 R 不能同时选择区间 [3,3] 和区间 [1,4]，因为这两个区间同时包含下标 3。
数据范围
对于所有测试数据，保证：
1≤n≤5×105，0≤k<220；
对于所有 1≤i≤n，均有 0≤ai<220。
特殊性质 A：对于所有 1≤i≤n，均有 ai=1。
特殊性质 B：对于所有 1≤i≤n，均有 0≤ai≤1。
特殊性质 C：对于所有 1≤i≤n，均有 0≤ai≤255。
参考答案
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
int n, k, a;
int dp[MAXN];
//存储每种异或和最后一次出现的下标
map<int, int> m;
int main() {
cin >> n >> k;
int qzh = 0;
m[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> a;
qzh ^= a;
dp[i] = dp[i-1];
if (m.find(k ^ qzh) != m.end()) dp[i] = max(dp[i], dp[m[k ^ qzh]] + 1);
m[qzh] = i;
}
cout << dp[n];
return 0;
}