正题

题目链接:https://www.luogu.com.cn/problem/P3760

题目大意

给出\(n\)个数字的一个序列\(a\)，求它所有区间和的异或和

\(n\leq 10^5,\sum a_i\leq 10^6\)

解题思路

开始写了个前缀和\(+FFT\)发现要卡常然后就换了个方法。

每一个位分开考虑，现在要求有多少个区间和的第\(k\)位是\(1\)。

设\(sum\)为区间和，那么为了方便计算我们要把\(and\)操作转换一下。就有\(sum\% 2^{k+1}\in[2^{k},2^{k+1})\)。

看起来好像更复杂了，其实没有，因为\(2^k\)我们可以直接枚举，那么对于模\(2^{k+1}\)次方意义下在\([2^{k},2^{k+1})\)范围内的区间和就符合要求。

这个就是树状数组的活了

时间复杂度\(O(n\log^2 n)\)（反正是\(log\)，\(\sum a_i\)算和\(n\)同级得了）

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) (x&-x)
using namespace std;
const int N=1<<20;
int n,a[N],t[N],ans,lim;
void Change(int x,int val){
x++;
while(x<=lim){
t[x]+=val;
x+=lowbit(x);
}
return;
}
int Ask(int x){
int ans=0;x++;
while(x){
ans+=t[x];
x-=lowbit(x);
}
return ans;
}
int Query(int l,int r)
{return Ask(r)-Ask(l-1);}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]+=a[i-1];
}
for(int lg=1;lg<=20;lg++){
lim=(1<<lg);
int k=lim>>1,tmp=0;Change(0,1);
for(int i=1;i<=n;i++){
int w=a[i]%lim;
if(w>=k)tmp+=Query(w+1,lim-1)+Query(0,(w+k)%lim);
else tmp+=Query(w+1,w+k);
Change(w,1);tmp%=2;
}
for(int i=1;i<=n;i++)Change(a[i]%lim,-1);
if(tmp&1)ans|=k;Change(0,-1);
}
printf("%d\n",ans);
}