题目描述
给定一个长度为 n 的数组 a，请问有多少个子数组是'神奇数组'。 换句话说，在数组 a 中存在多少对下标 l 和 r (1≤l≤r≤n) 满足： a_l ⊕ a_{l+1} ⊕ ... ⊕ a_r = a_l + a_{l+1} + ... + a_r 其中 ⊕ 表示按位异或运算。
输入格式
第一行输入一个整数 n，表示数组 a 的长度。 第二行输入 n 个整数，表示数组 a 的值。 数据保证 1 ≤ n ≤ 2×10^5，0 ≤ a_i < 2^20。
输出格式
输出一个整数表示答案。
解题思路
异或运算可以视为不进位加法。如果两个二进制数相加时没有产生进位，那么它们的异或值等于相加的值。该性质推广到多个数也成立。因此，对于一个'神奇数组'来说，每一个比特位最多只有一个数在该位为 1。如果某个比特位不止一个数在该位为 1，那么在相加时就会产生进位，导致异或和不等于和。
根据这个性质，我们需要枚举每个数作为数组的左边界 l，看最多有多少个右边界 r 使得区间 [l, r] 满足性质。由于左端点固定时，一旦冲突出现（即某一位有两个 1），继续向右扩展只会增加冲突，不会消除，因此右边界具有单调性。我们可以使用双指针来维护区间。
方法一：前缀和 + 双指针
维护前缀和数组和前缀异或数组，通过查询区间和与区间异或值来判断合法性。复杂度 O(n)。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=2e5+10;
ll a[N];
ll preSum[N], x[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n; cin>>n;
preSum[0]=0; x[0]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
preSum[i]=preSum[i-1]+a[i];
x[i]=(x[i-1]^a[i]);
}
int i=1,j=1;
ll cnt=0;
(i<=n&&j<=n){
((x[i]^x[j])==(preSum[j]-preSum[i])){
cnt+=j-i;
j++;
}
i++;
}
cout<<cnt<<;
;
}
