异或

P3760

对于连续区间，可以想到用前缀和\(s[j]-s[i-1]\)表示\(\sum_{k=i}^{j}a[k]\)。

那么，对于答案每一位\(k\)，求出有多少\(s[j]-s[i]\)第\(k\)位为1。

那么，从头到尾扫描\(s[j]\),用权值树状数组(两个，一个维护第k位是0，一个维护第k位是1)维护之前的\(s[i]\),对这一位的答案有贡献的只有那些第k位为1且第k位向右的数比s[i]第k位向右的数大的或者第k位为0且第k位向右的数不比s[i]第k位向右的数大的。

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
#define lowbit(x) (x&-x)
using namespace std;
const int N=1e5+10,C=1e6+10;
int s[N],a[N],f[C][2];
int n,maxn,ans;
void change(int i,int x,int d){
    while(x<C)f[x][i]+=d,x+=lowbit(x);
}
int sum(int i,int x){
    int ans=0;
    while(x>0)ans+=f[x][i],x-=lowbit(x);
    return ans;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]),s[i]=s[i-1]+a[i],maxn=max(maxn,s[i]);
    for(int v=0;v<=20;++v){
        if((1<<v)>maxn)break;
        int cnt=0;
        memset(f,0,sizeof f);
        change(0,1,1);
        for(int i=1;i<=n;++i){
            int tmp=s[i]&((1<<v)-1),type=(s[i]>>v)&1;

            if(type)cnt+=sum(1,C-1)-sum(1,tmp+1)+sum(0,tmp+1);
            else cnt+=sum(0,C-1)-sum(0,tmp+1)+sum(1,tmp+1);
            change(type,tmp+1,1);
        }
        if(cnt%2)ans|=(1<<v);
    }

    printf("%lld",ans);
    return 0;
}