题目链接

题解

对于数组: $0,1,2,...[l,...,mid,...,r],且‘r-l+1‘为偶数$,
记$all=[0,1,...,r]的异或和,pre=[0,1,...,l-1]的异或和,lef=[l,...,mid]的异或和,rig=[mid+1,..,r]的异或和$

如果lef == rig, 则lef ^ rig = 0, 推出 $\to$ [l, ..., r]的异或和为0
即: $(lef=rig)\to ([l,...,r]的异或和为0)$

但反过来是否成立呢?

根据 参见 的 异或和为0的任意可拆分性
如果[l, ..., r]的异或和为0, 则一定有: [l, ..., mid]的异或和 等于 [mid+1, ..., r]的异或和

---

因此, 以r为结尾的 满足要求的区间 (也就是[l, ... r]), 此时满足: all == pre, 因此, 用map记录, 找所有pre为all的个数即可.

下标从0开始, odd为 所有 奇数下标的 异或前缀和; even为 所有 偶数下标的异或前缀和.

但一定要注意, 比如对于r为偶数的情况: [0, 1, 2, 3, 4, 5, 6], 他的所有可能的答案区间: [5, 6] [3, 4, 5, 6] [1, 2, 3, 4, 5, 6]
即, 他的pre, 一定是存在的, 长度>= 1; 因为, 区间左端点最极限取到1, 而1的左侧还有0
但是, 对于r为奇数: [0, 1, 2, 3], 他的区间: [2, 3] [0, 1, 2, 3]
对于[0, 1, 2, 3], 他的pre应该为0, 但是, sum[ l - 1]是不存在的, 即他的pre, 已经越界了!!!
因此, 对于前缀和 [l, r]区间问题, 一定要注意: 边界情况; 当l == 0时, 此时的sum[ r] - sum[ l - 1]中的, l-1是不存在的

因此, 要提前加入: odd[ 0] = 1