有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个，两个人轮流操作，每次可以从一堆中拿走任意正数个石子，并可以将剩余石子合并到另一堆中（也可以不合并）。每次询问给定 $l$ 和 $r$ ，求 $[l,r]$ 中有多少个子段的石子单独拿出来进行游戏可以先手必胜。

$n,q\le 10^5, a_i\le 10^6$

结论：奇数堆时先手必胜，偶数堆时 $\oplus{(a_i-1)} \neq 0$ 时先手必胜。

证明：考虑数学归纳法。

1堆时显然先手必胜；2堆时双方都不可能进行合并操作，此时被迫拿完一堆的就输了，所以考虑将两堆数量都减1后当作nim游戏。

对于大于2的偶数，我们仍然按照上面的逻辑，每堆数量都减1后当作nim游戏。

对于大于2的奇数，我们考虑如何操作能将局面变为先手必败。我们考虑操作数量最多的堆，设该堆有 $x$ 个。设第2大的堆有 $y$ 个，第3大的堆有 $z$ 个。显然除了最大的两堆之外的堆减1后的异或和 $S$ 有 $S\le 2*(z-1)$ ，我们只需要将 $y$ 补至 $S+1$ 即可。注意到 $x+y\ge 2*z\ge S+2$ ，所以在将最大的堆拿走至少1个后仍然可以将次大的堆补至 $S+1$ 。所以对于奇数堆我们有将其变为偶数堆先手必败的情况。

有了上述结论之后，我们每个询问就变成了求区间内长度为奇数的子段数加减1后异或和不为0的长度为偶数的子段数，这个问题显然可以变为总子段数减去异或和为0的长度为偶数的子段数，然后用莫队求解。