感想:
真的不会做这种题,虽然已经想到了异或和这种题要按位求贡献,但是偶数还有区间这个问题想不出来怎么解决。后来看了别人的题解,想了好久才终于想明白怎么一回事了。

思路:
首先,一般异或和这种题都是按位求贡献这个方向是没错的。此时要算一个区间内的异或和的这一位是否有贡献(也就是区间异或和的这一位是否为1)可以通过异或前缀和来O(1)得到。
什么意思呢?首先我们先求一个异或前缀和,假设是sum数组,那么如果知道这个区间内异或和的这一位是否为1,只需要看sum[l-1]^sum[r]是不是1就好了。
为什么?假如sum[l-1]这一段前缀和是这一位是1,sum[r]这一位是0,那么说明在l到r这一段异或和肯定是1,因为1要和1做异或运算才能变为0。因此可以发现判断区间的某一位异或和是否为1可以通过前缀和来解决。
然后就是偶数区间怎么解决了,这个比较简单,只需要判断左右端点是不是同为奇数或者偶数就好了。
l,r就是加一个限制就好了。
然后开始算法部分:
我们维护一个dp[k][j]数组,枚举第i位,k表示所有的左端点-1中的第i位前缀和为1/0,并且j表示位置为奇数/偶数的个数。(为什么是左端点-1,因为sum[l-1]^sum[r],上面已经说过了)
因为区间至少是[l,r],所以我们枚举右端点从l开始,更新dp数组(假设枚举的点为j):
dp[(a[j-l]>>i)&1][(j-l)&1]++;
表示:左端点-1这一位的前缀和是不是1,并且它的位置是奇数还是偶数。
对于这个右端点,它做的贡献就是:
dp[((a[j]>>i)&1)^1][j&1]*(1<<i)
表示它跟左端点-1这一位的前缀和异或是1(比如右端点是1,那它需要左端点-1的点是0才行,反之亦然)并且位置都是奇数/偶数的点能做2^i的贡献。
最后如果超过r了,要把数量减一下,因为不减的话求出来的区间长度就超过r了。

代码:

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<map>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7 
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=5e5+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

ll dp[2][2];

ll a[maxn];

int main(){
    int n,l,r;
    scanf("%d%d%d",&n,&l,&r);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        a[i]=a[i-1]^a[i];
    }
    if(l&1) l++;
    if(r&1) r--;
    if(l>r){
        printf("0");return 0;
    }
    ll ans=0;
    for(int i=0;i<32;i++){
        ll tmp=(1ll<<i);
        memset(dp,0,sizeof(dp));
        ll num=0;
        for(int j=l;j<=n;j++){
            dp[(a[j-l]>>i)&1][(j-l)&1]++;
            num=(num+dp[((a[j]>>i)&1)^1][j&1])%mod;
            if(j>=r) dp[(a[j-r]>>i)&1][(j-r)&1]--;
        }
        ans=(ans+num*tmp%mod)%mod;
    }
    printf("%lld",ans);
    return 0;
}