abc365 E-Xor Sigma Problem
思路
本题首先可以想到用前缀异或和维护，我们记作\(b_i=a_1\oplus a_2 \oplus ··· \oplus a_i\)，所求的式子就变成了\(\sum^{n-2}_{i=0}\sum^n_{j=i+2}b_i\oplus b_j\)，直接求是\(O(n^2)\)的，考虑如何快速求出\(\sum^{x-1}_{i=0}b_i\oplus b_x\)
因为这是位运算，所以我们不难想到按位考虑，我们记\(g_{i,j}\)为当前考虑范围内第\(q\)位为\(p(0,1)\)的个数，我们动态维护\(b1...i\)总的\(g_{q,p}\)，当我们枚举到第\(b_{i+1}\)时，如果此时的第\(j\)位为\(1\)，那么\(g_{i,0}\)将是有贡献的，反之同理
代码
#include<bits/stdc++.h>
using namespace std;
inline long long read(){
long long ans=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-f;
c=getchar();
}
while(c>='0'&&c<='9'){
ans=(ans<<3)+(ans<<1)+c-48;
c=getchar();
}
return ans*f;
}
void write(long long x){
if(x<0){
putchar('-');
x=-x;
}
if(x<10) putchar(x+48);
else{
write(x/10);
putchar(x%10+48);
}
}
long long n;
long long a[200005],b[200005];
long long g[35][2];
long long ans;
signed main(){
n=read();
for(long long i=1;i<=n;i++){
a[i]=read();
b[i]=a[i]^b[i-1];
}
for(long long i=0;i<=28;i++) g[i][0]++;//将b[0]加进去
for(long long i=1;i<=n;i++){
for(long long j=0;j<=28;j++){
ans+=g[j][bool((b[i])&(1<<j))^1]*(1<<j);//按位统计答案
}
for(long long j=0;j<=28;j++){
g[j][bool((b[i])&(1<<j))]++;//按位更新g数组
}
}
for(long long i=1;i<=n;i++) ans-=a[i];//除去长度为1的区间
write(ans);
return 0;
}