P3917 异或序列

纯暴力(Theta(n^3))，前缀和优化(Theta(n^2))，因(n)为十万级别无法通过本题。

考虑将每个二进制位的贡献分开来算。

对于二进制第(i)位，若当前此位为1，则只有与0亦或才能产生贡献，反之亦然。

则对于每一个二进制位，维护数组(val[i][0/1])，代表这个位置上(0/1)的个数。

则贡献为(w=val[i][!t]*(1<<i))，注意总贡献要开(long long)。

注意对于每个数只计算它与前面产生的贡献，这样就不会重复计算。

时间复杂度(Theta(nlogn))

代码如下，仅供参考：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,a[maxn];
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
int val[50][2],cnt;
long long ans;
inline void insert(int x){
	for(int i=0;i<=30;i++){
		int t=(((1<<i)&x)!=0);
		ans+=(1ll<<i)*val[i][!t];
		val[i][t]++;
	}
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read()^a[i-1];
	insert(0);
	for(int i=1;i<=n;i++)
		insert(a[i]);
	printf("%lld
",ans);
	return 0;
}

深深地感到自己的弱小。