题目描述

难度分:$1404$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(0 \leq a[i] \lt 2^{20})$。

$a$有多少个非空连续子数组，满足元素和等于元素异或和？

输入样例$1$

4
2 5 4 6

输出样例$1$

5

输入样例$2$

9
0 0 0 0 0 0 0 0 0

输出样例$2$

45

输入样例$3$

19
885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1

输出样例$3$

37

算法

双指针

异或运算本身就是不进位的加法（二进制下的不进位），因此异或和不会超过元素和，有如下的单调性成立：

1. 如果一个子数组满足异或和等于元素累加和，那么把这个子数组缩短肯定也满足。
2. 如果一个子数组不满足异或和等于元素累加和，那么把这个子数组扩大肯定也不满足（因为不相等已经意味着元素和进位了，再继续扩大元素和也不可能相等的）。

这样我们就可以枚举子数组的右端点$r \in [1,n]$，初始化左指针$l=0$，对于一个刚好满足$l \lt r$且$s[r]-s[l]=eor[r] \oplus eor[l]$的$l$（$s$表示$a$的前缀和数组，$eor$表示$a$的前缀异或和数组），对于任意$l \lt j \leq r$，肯定都有子数组$[j,r]$的异或和等于元素累加和，产生了$r-l$个符合条件的子数组，在遍历$r$的过程中统计所有右端点对答案的贡献即可。

复杂度分析

时间复杂度

整个过程是一个经典的双指针算法，子数组右边界指针$r \in [1,n]$，由于左指针$l$随着$r$的右移不会回退，因此算法整体的时间复杂度就是$O(n)$。

空间复杂度

开辟了前缀和数组$s$以及前缀异或和数组$eor$，和原数组$a$的规模相同，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
typedef long long LL;

const int N = 200010;
LL s[N];
int n, a[N], eor[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
        eor[i] = eor[i - 1]^a[i];
    }
    LL ans = 0;
    int l = 0;
    for(int r = 1; r <= n; r++) {
        while(l < r && (eor[l]^eor[r]) != s[r] - s[l]) l++;
        ans += r - l;
    }
    printf("%lld\n", ans);
    return 0;
}