考虑什么时候先手必胜，什么时候后手必胜。
显然的，一堆石子肯定是先手必胜。
考虑两堆石子。如果两堆石子都只有一颗那么是后手必胜。只剩一堆石子先手必胜。所以两个人一定都不敢拿完或者合并。那这个游戏就能转化为，有两堆石子（数量分别为原来的两堆石子 $-1$），两个人依次拿，谁先把两堆拿完谁就赢。这是一个典型的 Nim 游戏。结论即为两堆石子数量不同先手必胜，反之必败。
考虑三堆石子。设数量分别为 $a,b,c$，均为正整数。不失一般性地，假设 $0 < a \leq b \leq c$，那么先手可以合并 $a$ 和 $c$ 两堆，在 $c$ 中拿掉 $a+c-b$ 颗石子。只需证明 $0 < a+c-b \leq c$ 即可。因为 $a+c-b \geq a$，又由于 $a>0$，显然有 $a+c-b>0$；因为 $a+c-b=c-(b-a)$，又 $b \geq a$，所以 $b-a \geq 0$，于是 $a+c-b>0$。因此无论如何都可以拿成两堆相同的。所以先手必胜。
考虑四堆石子。根据三堆石子的结果，两个人一定都不敢拿完或者合并。那么最后肯定又是每堆拿成一个，因此也是 Nim 游戏，每堆石子数减一的异或和不为 $0$ 先手必胜，否则先手必败。
考虑五堆石子。不妨先全减 $1$。我们现在要证明操作可以使剩下四堆石子异或和为 $0$。考虑小的三堆，假设最高位是 $2^k$，那么异或和不会超过 $2^{k+1}-1$。而最大的两堆和一定超过这个值。但是如果最大的两堆拿不到更小怎么办？考虑继续构造。最大的一堆必须要拿，因此可以拿掉一些石子使其最高位和次大值相同。钦定次大值不合并，那么最高的一些位就被消掉了。这样等价于至少三个数最高位相同，那么如果奇数个相同肯定要把原先钦定的这一堆最高位拿掉，那么此时下面的位就可以任取；如果偶数个相同，那就考虑取下一位为 $1$ 的。这样递归下去，归纳可知一定有解。（这里的最高位可能不止一位，不止一位可以当成一位缩掉）但是这样有问题，因为合并的有一堆不能减 $1$。然而我们发现最多的一堆不管怎么样都是拿的，这堆减不减也没关系。因此五堆石子先手必胜。
六堆石子同四堆。七堆石子和五堆类似。
这样总结就可以发现，奇数堆先手必胜；偶数堆每堆 $-1$ 异或和为 $0$ 先手必败，否则先手必胜。
也就是我们可以把子区间总数减去长度偶数且石子数 $-1$ 异或和为 $0$ 的区间。那维护前缀即可。
这个东西显然可以使用莫队做。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, q, a[100005], s[100005], ans[100005], s1, s2;
int kl[2005], kr[2005], bel[100005];
unordered_map<int, int> m1, m2;
struct que{
int l, r, id;
}Q[100005];
void add(int pos){
if (pos & 1){
s1 += m1[s[pos]];
m1[s[pos]]++;
}else{
s2 += m2[s[pos]];
m2[s[pos]]++;
}
}
void del(int pos){
if (pos & 1){
m1[s[pos]]--;
s1 -= m1[s[pos]];
}else{
m2[s[pos]]--;
s2 -= m2[s[pos]];
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] ^ (a[i] - 1);
for (int i = 1; i <= q; i++){
cin >> Q[i].l >> Q[i].r;
Q[i].l--;
Q[i].id = i;
}
int kc = 314, ks = (n + kc - 1) / kc;
for (int i = 1; i <= ks; i++){
kl[i] = kr[i - 1] + 1;
kr[i] = kl[i] + kc - 1;
}
kr[ks] = n;
for (int i = 1; i <= ks; i++)
for (int j = kl[i]; j <= kr[i]; j++)
bel[j] = i;
sort(Q + 1, Q + 1 + q, [](que a, que b){if (bel[a.l] != bel[b.l]) return bel[a.l] < bel[b.l]; else return a.r < b.r;});
int l = 1, r = 0;
s1 = s2 = 0;
for (int i = 1; i <= q; i++){
while (l > Q[i].l)
add(--l);
while (r < Q[i].r)
add(++r);
while (l < Q[i].l)
del(l++);
while (r > Q[i].r)
del(r--);
int len = Q[i].r - Q[i].l;
ans[Q[i].id] = len * (len + 1) / 2 - s1 - s2;
}
for (int i = 1; i <= q; i++)
cout << ans[i] << "\n";
return 0;
}