NC14414

感受
思路很常规，二进制拆位算贡献，但是苦逼的我debug一下午，代码实现能力有待提高

思路

常规做法，枚举区间左端点L，如何找右端点呢？
异或题，肯定要想到二进制拆位，于是，问题就简单转化为对于某一二进制位，算出这个位对答案的贡献。

贡献 = ((ll)1<<i) * (区间种数) 

于是，考虑怎么算区间种数？
区间有什么特性吗？显然，把区间里的每个数拆成二进制，统计第i位的值，作一个求和，如果为奇数，那么对答案有贡献，否则无贡献。
于是，我们言归正传，看看此题

首先题目有两个限制条件：
（1）区间长度为偶数
（2）区间长度属于[l, r]
其实，限制(2)很好转化，我们枚举左端点L，那么右端点取值为[L + l - 1, min(L + r - 1, n)]（如果区间不合法，就肯定无贡献，比如区间[5, 2]）
如何满足条件(1)呢？
其实也很简单，右端点的取值奇偶性与L的奇偶性相反即可，自己画画就知道了。

那我们考虑最后一个问题，如何统计枚举左端点为L的答案呢？
设右端点取值为[R1, R2]，会成为的R有以下特性
（1）R的奇偶性与L的奇偶性不同
（2）L到R中，对应二进制位为1的个数为奇数
显然暴力check会T
所以，我们需要做几个前缀和

sum[pos][i] 前pos个数中，二进制第i位为1的个数之和
num[0/1][pos][i][0/1];///前pos个数中, 考虑[偶/奇]下标 sum[1-pos][i]为[偶数/奇数]的个数
区间个数 = num[(L - 1) % 2][R2][i][!(sum[L - 1][i] % 2)] - num[(L - 1) % 2][R1 - 1][i][!(sum[L - 1][i] % 2)];

AC代码

#include <bits/stdc++.h>
#define ls o << 1
#define rs o << 1 | 1
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
int num[2][maxn][35][2];///前pos个数中, 考虑[偶/奇]下标 sum[pos][i]为[偶数/奇数]的个数
int sum[maxn][35];///0 - 32  sum[pos][i]前pos个数中,第i位为1的个数的奇偶性
int n, l, r;

void solve(int x, int pos){
    int i = 0;
    while(x){
        if(x % 2){
            sum[pos][i] = 1;
        }
        else{
            sum[pos][i] = 0;
        }
        x /= 2; i++;
    }
}
void solve1(){
    for(int pos = 1; pos <= n; pos++){
        for(int i = 0; i < 35; i++){
            sum[pos][i] += sum[pos - 1][i];
            if(sum[pos][i] % 2){
                num[pos % 2][pos][i][1] = 1;
                num[pos % 2][pos][i][0] = 0;
            }
            else{
                num[pos % 2][pos][i][0] = 1;
                num[pos % 2][pos][i][1] = 0;
            }
        }
    }
    for(int k = 0; k <= 1; k++){
        for(int pos = 1; pos <= n; pos++){
            for(int i = 0; i < 35; i++){
                for(int j = 0; j <= 1; j++){
                    num[k][pos][i][j] += num[k][pos - 1][i][j];
                }
            }
        }
    }

}
int main(){
    int tmp;
    scanf("%d%d%d", &n, &l, &r);
    for(int i = 1; i <= n; i++){
        scanf("%d", &tmp);
        solve(tmp, i);
    }
    solve1();
    int L, R1, R2;
    ll ans = 0;
    for(L = 1; L <= n; L++){
        R1 = l + L - 1; R2 = min(r + L - 1, n); if(R1 > R2) continue;
        for(int i = 0; i < 35; i++){
            int get;
            get = num[(L - 1) % 2][R2][i][!(sum[L - 1][i] % 2)] - num[(L - 1) % 2][R1 - 1][i][!(sum[L - 1][i] % 2)];
            ans = ans + ((ll)1 << i) % mod * get % mod;
            ans %= mod;
        }
    }
    printf("%lld\n", ans);
    return 0;
}
/*
2 1 2
4 4

*/