思路
题目要求我们计算任意一子段的异或和。
根据异或的性质,我们用s[N]存放异或前缀和,s[i]表示a[1]到a[i]的异或和。
如果我们想知道a[i]到a[j]的异或和, 只需要s[j] ^ s[i - 1]即可, 相同的部分异或清0。
但是统计总和仍需要$O(n^2)$的复杂度
求每一段异或和,可以理解为选个两个前缀和异或
我们可以在草稿纸上将例子以这种形式写出:
s[0]:000
s[1]:001
s[2]:011
s[3]:000
s[4]:100
s[5]:001
我们从每位来看,在第1位上,s[1]和s[0]异或可使第一位结果为1, s[2]和s[0]异或可使第一位结果为1, s[3]和s[1]、s[2]都可以,只要从前往后记录0的个数和1的个数。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
LL a[N], s[N], ans;
int n;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
s[i] = s[i - 1] ^ a[i];
}
for(int j = 0; j < 21; j++) //2^20是21位!!
{
int c0 = 1, c1 = 0; //记录0-i内0和1的个数
LL res = 0;
for(int i = 1; i <= n; i++)
{
if(s[i] >> j & 1 == 1)
res += c0, c1++;// 只与前面的0配对
else
res += c1, c0++;// 只与前面的1配对
}
ans += res * (1 << j);
}
printf("%lld", ans);
return 0;
}