C++ 算法题：统计满足异或和等于和的子数组数量

题目描述

给定一个长度为 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;
    while(i<=n&&j<=n){
        ((x[i]^x[j])==(preSum[j]-preSum[i])){
            cnt+=j-i;
            j++;
        }
         i++;
    }
    cout<<cnt<<;
     ;
}