题解：小AA的数列

又是求异或和的和的常见套路——按位计算，即计算二进制中每一位的贡献。

需要注意的是，题目要求的不仅要区间长度在[L,R],而且区间长度必须是偶数（因为这个debug了好久qwq）

我们先来简化下题目。

我们假设只考虑一个二进制位x，并且区间长度也可以为奇数，那么这个怎么做呢？

很简单，我们为了方便处理，先做个前缀和，sum[i]sum[i]表示，前i个数字中，二进制第x位为1的数字的个数。

然后，我们就来统计答案，为了好计算，我们肯定要先固定区间的一个端点，于是，我们先枚举左端点l,那么，明显的，对答案有贡献的只有第x位为1的个数是奇数的区间，每个这样的区间都会产生贡献2^{x-1}2
x−1
的贡献，那么，我们统计有几个这样的区间就行了。

注意到，因为左端点固定，所以一个区间中，第x位为1的数字的个数即是sum[i]-sum[l-1]sum[i]−suml−1

因为l是确定的，所以sum[l-1]sum[l−1]的奇偶性也是确定的，那么，我们只需要统计所有满足条件的右端点i中，sum[i]sum[i]的奇偶性和sum[l-1]sum[l−1]相反的个数即可。

那么，我们开个辅助数组cnt[i][0/1]cnt[i][0/1]表示前i个数字中，sum[i]sum[i]为偶/奇的个数，那么，只要我们预处理好sum[i]sum[i]和cnt[i]cnt[i]这两个数组，我们就可以直接O(1)O(1)计算出左端点确定时，对答案有贡献的右端点的数量，这个数量再乘单个的贡献，即为只考虑一个x位时的答案。

这样，就完成了。

那么，现在来加强下，我们再令区间长度必须为偶数，这个怎么办呢？

还是同样的方法，我们确定了左端点，那么，对于一个区间长度的奇偶性合法的右端点i来说,i+2,i+4...也是合法的，于是，我们将原序列奇偶分割，即，我们统计cnt的时候(sum就不用了，sum必须保持值正确)，只用i-2去更新i，这样，奇偶性合法的就在一起被统计到了（注意特判1）

然后，计算的时候，由于又要区间长度为[L,R]，所以我们再修改下左右端点，使其从合法的位置开始即可~

然后，再把每个二进制位都计算出来，就是最终答案了
来源：https://blog.nowcoder.net/n/4dacd8e372de4199a30442b4eee1849a

代码如下：
#include<bits/stdc++.h>
#define LL long long
#define INF 1000000007
using namespace std;
int n, l, r, a[100005], ans[100005][31], sw[100005][31][2];
LL ans=0;

void solve()
{
for(int i=1; i<=n; i++)
{
for(int j=0; j<31; j++)
{
ans[i][j]=ans[i-1][j]+((a[i]>>j)&1);
if(i!=1)
{
sw[i][j][0]=sw[i-2][j][0];
sw[i][j][1]=sw[i-2][j][1];
}
sw[i][j][ans[i][j]%2]++;
//printf("%d ",sw[i][j][1]);
}
//printf("\n");
}
for(int i=1; i<=n-l+1; i++)
{
int l1=i+l-1, r1=min(i+r-1,n);
if(l%2==1)
{
l1++;
}
if((r1-i+1)%2==1)
{
r1--;
}
if(l1>r1)
{
continue;
}
for(int j=0; j<31; j++)
{
if(l1>1)
ans=(ans+(1LL<<j)%INF(sw[r1][j][1-ans[i-1][j]%2]-sw[l1-2][j][1-ans[i-1][j]%2])%INF)%INF;
else
ans=(ans+(1LL<<j)%INFsw[r1][j][1-ans[i-1][j]%2]%INF)%INF;
}
}
}

int main()
{
scanf("%d%d%d",&n,&l,&r);
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
}
solve();
cout << ans << endl;
return 0;
}