小R有一个长度为 n的非负整数序列 a1,a2,...,an。定义一个区间 l,r的权值为 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。你需要帮助小R求出他能选出的区间数量的最大值。

需要用到的思想或方法：

  1. 异或运算性质
  2. 前缀异或
  3. 哈希表查询
  4. 贪心

异或运算

运算符^，运算过程即转化二进制，按位比较，异1同0。

前缀异或

为了方便，下面统一用1-based，不管是位置还是下标。

某位置i的前缀异或一般讲就是从开始到当前位置的连续异或

P[i] = a[1]⊕...⊕a[i]

这道题里要算区间异或，它和前缀异或的关系是

xor(l,r)=P[r]⊕P[l−1]

两边乘上P[r]

P[r]⊕xor(l,r)=P[l−1]

我们只要查询P[l-1]出现位置就能找到合法区间

哈希表

那么怎么查找呢，数组因为太大out了，所以要用到字典（红黑树），或者哈希表

使用时要包含头文件

#include <map> //字典，特点是按键排序
#include <unodered_map> //哈希表，无序

作用简单来说就是提供自定义的映射关系（从key到value），可实现关系的高效储存和查询

用法（以哈希表为例）：

unordered_map <int, int> dict; //定义
unordered_map <int, int> dict{{1,1}{2,2}};//带初始化
auto it = dict.find(need);//查找
int elem = dict.at(3);//另一种查找
if(it != dict.end())...//找到该元素
cout<<dict[1]; //调用与数组类似

贪心

贪心是很简单的思想，体现在这道题里就是：

  1. 按右端点从小到大处理
  2. 对于每个右端点，选择左端点最靠右的合法区间（即最短区间）
  3. 保证新区间与已选区间不重叠

最后构建代码


#include <iostream>
#include <stdio.h>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector <int> a(n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int count = 0, x = 0, need,position=0;
    unordered_map <int, int> last_pos;
    last_pos[0] = 0;
    for (int i = 0; i < n; i++) {
        x ^= a[i];
        need = k ^ x;
        auto it = last_pos.find(need);
        if (it != last_pos.end() && it->second >=  position) {
            count++;
            position = i;
        }
        last_pos[x] = i;
        
    }
    cout << count << endl;
    return 0;
}