题目描述

符卡有一个长度为 $n$ 的整数数组 $a$，符卡认为一个区间 $[l, r]$ 是灵异区间当且仅当 $\bigoplus_{i=l}^r a_i = 0$，或者说这个区间内所有数字异或起来刚好等于 $0$。
符卡有特殊的魔法，可以把任意一个灵异区间翻转。具体来说，如果 $[l, r]$ 区间是灵异区间，那么符卡就可以对这个区间使用魔法，整个数组就会变成 $a_1, a_2, \dots, a_{l-1}, a_r, a_{r-1}, \dots, a_l, a_{r+1}, a_{r+2}, \dots, a_n$。
现在符卡可以使用任意次数的魔法，符卡希望最后得到的数组的灵异区间数量能够尽可能多，你能告诉她最后最多有多少个灵异区间吗？

输入格式

第一行一个正整数 $n$，表示数组长度。
第二行 $n$ 个非负整数 $a_1, a_2, \dots, a_n$ 表示整个数组。

输出格式

输出一行一个整数，表示符卡使用任意次魔法后灵异区间最多有多少个。

输入输出样例

输入 #1

3
1 1 1

输出 #1
2

输入 #2
4
3 1 2 3

输出 #2
2

对于如何找到灵异区间我们前面说到过,对整个数组求前缀异或,如果一个区间左右两端的数相等那么这段区间异或和为0。现在对于每个灵异区间要对它翻转,我们要考虑翻转过后对整个数组的应该。每个灵异区间的位置有三种可能。第一种:一个灵异完整地包裹在另一个灵异区间里面,第二种:一个灵异区间部分地包裹在另一个灵异区间里面,第三种:一个灵异区间独立存在,不与其他灵异区间相交。
9
所以灵异区间翻转不会产生新的灵异区间或者使灵异区间减少,所以只用统计灵异区间的个数,不用考虑翻转

#include<iostream>
#include <unordered_map>
#include<vector>
#include<map>
using namespace std;
int main(){
    int n,sum=0;
    cin>>n;
    vector<int>arr(n+1,0);
    unordered_map<int,int>cnt;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        arr[i]^=arr[i-1];
    }
    for(auto &x:arr)
    cnt[x]++;
    for(auto &[_,c]:cnt)
    sum+=c*(c-1)/2;
    cout<<sum;
}