题目内容

给你一个序列$a$:$a[1],a[2],a[3],...,a[n]$。给一个数$x$，求满足下列条件的非空区间$[L,R]$的个数：

题面描述

给定一个序列 $a$：$a[1], a[2], a[3], \dots, a[n]$，以及一个数 $x$，请计算满足以下两个条件的非空区间 $[L, R]$ 的个数：

1. 区间 $[L, R]$ 中所有元素的异或值等于 $x$，即 $a[L] \oplus a[L+1] \oplus \dots \oplus a[R] = x$。
2. 区间的长度为偶数，即 $(R - L + 1) \bmod 2 = 0$。

思路

对于一段区间$[l,r]$的异或和等于[1,r]的异或和异或[1,l-1]的异或和，那么对于奇数下标的前缀异或和，如果与之前的奇数下标的前缀异或和异或为$x$说明答案可以++，偶数同理，我们用两个哈希表分别记录偶数与奇数的前缀异或和为w ^ x的区间那么如果当前下标奇偶性相同且前缀异或和为$w$那么这段$[l,r]$的区间异或和就是$x$