对于每个二进制位考虑有多少区间和这一位上为1
从前往后扫每个前缀和,如果当前这个前缀和某一个二进制位上为1,因为区间和由这个前缀和减去前面的前缀和得来,如果减去了这一位为0的前缀和,那么 减去的前缀和的 比这一位更小的位 组成的数 要小于等于 当前前缀和 比这一位更小的位 组成的数,区间和的这一位才为1,这样子减是不会产生借位的;反之,如果减去了这一位为1的前缀和,那么 减去的前缀和的 比这一位更小的位 组成的数 要大于 当前前缀和 比这一位更小的位 组成的数,产生借位,减出来这一位才为1;如果当前这个前缀和某一个二进制位上为0就反过来
我 打 字 带 空 格
要统计在某个区间内的数的个数,用树状数组救星了
#include<bits/stdc++.h>
#define il inline
#define re register
#define LL long long
#define db double
#define ldb long double
#define eps (1e-7)
using namespace std;
const int N=300000+10;
const LL mod=20021101;
il LL rd()
{
LL x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
LL m,g[N];
struct BIT
{
int m,c[(1<<20)+10];
il void init(int mm){m=mm,memset(c,0,sizeof(c));}
il void add(int x,int y){++x;while(x<=m) c[x]+=y,x+=x&(-x);}
il int pre(int x){++x;int an=0;while(x>=1) an+=c[x],x-=x&(-x);return an;}
il int sum(int l,int r){return pre(r)-pre(l-1);}
}a[2];
int main()
{
m=rd();
for(int i=1;i<=m;i++) g[i]=g[i-1]+rd();int a2=0;
a[0].init(g[m]+1),a[1].init(g[m]+1);
for(int j=0;j<20;j++)
{
if((1<<j)>g[m]) break;
int cn=0,ma=(1<<j)-1;
for(int i=0;i<=m;i++)
{
int x=g[i]&ma,y=(g[i]>>j)&1;
cn+=a[y^1].sum(0,x)+a[y].sum(x+1,ma);
a[y].add(x,1);
}
a2^=(cn&1)<<j;
for(int i=0;i<=m;i++)
{
int x=g[i]&ma,y=(g[i]>>j)&1;
a[y].add(x,-1);
}
}
printf("%d\n",a2);
return 0;
}