首先借鉴前缀和的想法，将区间操作的时间简化为O(1)，s[i]数组存储的是a[1]到a[i]元素的异或和，可以看出s[j] ^ s[i - 1] = a[i] ^ a[i + 1] ^…^ a[j - 1] ^ a[j]，这是很显然的。

接下来可以遍历区间的左右端点，时间是O(n^2)的

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

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

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

//a[N]中每个数字都是20位的二进制数，所以区间异或和取决于同一位1的奇偶数

//60分

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] ^ a[i];

    LL ans = 0;

    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j ++ )
            ans += s[j] ^ s[i - 1];

    cout << ans << endl;

    return 0;
}

但是会卡时间，要对时间优化

由于所求的是所有s[i - 1] ^ s[j]的和，从数的二进制表示出发，给的范围是21位，每一个二进制位最终异或的结果只会是0或者1，就可以遍历这21位每一位，分别求出对总和的贡献。

对于每一个s[i] (这里i枚举的是区间[L, R]的右端点，不需要枚举左端点，只用找前面的0和1)，如果s[i]的第j位是1的，前面的s[a]的第j位是0，s[b]的第j位是1，那么s[i] ^ s[a]的第j位就是1，s[i] ^ s[b]的第j位就是0，s[i] ^ s[b] == 1会对最后的区间和产生贡献，而s[i] ^ s[a] == 0不会，这样只需要统计s[0] ~ s[i]中第j位是0的数组元素的数量就可以得到以i位区间右端点的所有区间对总和(所有区间内异或后的和)。

(只需要以O(n)的时间遍历一次数组就可以得出，而不需要遍历两重端点)

具体来说，按照给的参考例子，数组1 2 3 4 5，对应的s数组为0 1 3 0 4 1(s[0] ~ s[5])

s[0] = 0 = 0 0 0 0, s[1] = 1 = 0 0 0 1, s[2] = 3 = 0 0 1 1, s[3] = 0 = 0 0 0 0, s[4] = 4 = 0 1 0 0, s[5] = 1 = 0 0 0 1

显然只用考虑二进制的前3位，第1位为0 1 1 0 0 1，从第一个元素开始，1之前只有s[0]为0，所以贡献为1，第二个1前有0 和 1，0的数量为1，贡献为1 + 1 = 2，第三个0前面有两个1，贡献为2 + 2 x 1 = 4，第四个0同样，贡献为4 + 2 x 1 = 6，最后的1前面有3个0，所以二进制第一位的总贡献为6 + 3 * 1 = 9。同理，二进制第二位，第三位的贡献为10 和 20，这样算出来区间和为39

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

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

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

//a[N]中每个数字都是20位的二进制数，所以区间异或和取决于同一位1的奇偶数

//100分

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] ^ a[i];

    LL ans = 0;

    for (int j = 0; j < 21; j ++ ) //枚举每一位，给的Ai范围是0 ~ 2^20
    {
        int c0 = 1, c1 = 0; //s[0]始终为0，所以多一个c0 = 1
        LL now = 0; //当前位的答案
        for (int i = 1; i <= n; i ++ )
            if (s[i] >> j & 1) now += c0, c1 ++ ; //s[i]的第j位是1
            else now += c1, c0 ++ ; //s[i]的第j位是0
        ans += now * (1 << j);
    }

    cout << ans << endl;

    return 0;
}

算是这题讲的最详细的题解了，点个赞再走呗