前缀和+按位贡献$O(n)$

$由于要求一段区间的异或值，可以采用前缀和事先枚举前缀的异或和，\\ 然后枚举每一段区间求其异或和O(n^2) 最简单能拿60\%分$

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N], s[N];
int n;

int main(){
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++){
        scanf("%d", &a[i]);
        s[i] = s[i - 1] ^ a[i];
    }

    int res = 0;
    for (int i = 1; i <= n; i ++){
        for (int j = 0; j < i; j ++){
            res += s[i] ^ s[j];
        }
    }
    printf("%d\n", res);
    return 0;
}

$优化采用二进制拆位贡献法，每个数一共有20位，只需要考虑，每个数每一位对结果的贡献即可\\ 例如：此题中实际利用了三位，模拟一下：\\ a[i]\ \ \ \ \ \ \ \ s[i]\\ 1: 001 \ \ \ 001\\ 2:010 \ \ \ 011\\ 3:011 \ \ \ 000\\ 4:100 \ \ \ 100\\ 5: 101 \ \ \ 001\\ 由于异或和前缀和能更好的理解，所以还是用上异或前缀和\\ 当前位为1，表示这个数当前位在前缀和中有贡献，当前位为0表示当前数这个位在前缀和没有贡献\\ 这样我们就可以找有贡献的区间了，同理要看这个数在[L + 1, R]之间是否有贡献，就可以用s[L] \oplus s[R]，如果为1就有贡献\\ 这样在求每一位可以影响哪些区间时就是找这个数当前位前面不同数(1时找0,0时找1）的个数, s[0]也要考虑在内，表示贡献整个前缀和\\ 例如i = 0，j=5时可以影响的区间是(0, 5], (3, 5], (4, 5]\\ i=0, j =4时可以影响的区间是(1, 4], (2, 4]$

#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long

using namespace std;

const int N = 100010;

int a[N], s[N];
int n;

signed main(){
    scanf("%lld", &n);

    for (int i = 1; i <= n; i ++){
        scanf("%lld", &a[i]);
        s[i] = s[i - 1] ^ a[i];
    }

    int res = 0;
    //当取2^20时，等于1 << 20, 一共21位
    for (int i = 20; i >= 0; i --){
        int n1 = 0, n0 = 1; //n1表示前面1的个数就是s[L]==1的情况，n0表示0的个数，包含s[0]
        for (int j = 1; j <= n; j ++){
            if ((s[j] >> i) % 2){
                res += n0 * (1 << i);
                n1 ++;
            }
            else{
                res += n1 * (1 << i);
                n0 ++;
            }
        }
    }
    printf("%lld\n", res);
    return 0;
}