Luogu

分析

容易想到拆位。则我们需要计算有多少对 $(i,j)$ 满足 $s_j-s_{i-1}$ 的第 $k$ 位是 $1$。

那么有两种情况：

• 如果 $s_j$ 的 $0\sim k-1$ 位小于等于 $s_{i-1}$ 的 $0\sim k-1$ 位，则 $s_j$ 和 $s_{i-1}$ 的第 $k$ 位不同时满足条件。
• 否则，$s_j$ 和 $s_{i-1}$ 的第 $k$ 位相同时满足条件（可以想一下退位的过程）。

如果满足条件的数是奇数则答案的这一位为 $1$。

于是可以从左往右枚举 $j$，并用两个树状数组维护第 $k$ 位为 $0/1$ 的 $s_{i-1}$ 的数量即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,L=1000000;

int n,s[N];

int c[L+10][2];
void modify(int x,int y) { for (++x;x<=L+1;x+=x&-x) c[x][y]^=1; }
int query(int x,int y) { int s=0; for (++x;x;x-=x&-x) s^=c[x][y]; return s; }

int main() {
    n=read();
    for (int i=1;i<=n;++i) s[i]=s[i-1]+read();
    int ans=0;
    for (int i=0;i<=20;++i) {
        memset(c,0,sizeof(c));
        modify(0,0); int flag=0;
        for (int j=1;j<=n;++j) {
            int p=(s[j]>>i)&1,q=s[j]%(1<<i);
            flag^=query(q,p^1);
            flag^=query(L,p)^query(q,p);
            modify(q,p);
        }
        if (flag) ans|=1<<i;
    }
    printf("%d\n",ans);
    return 0;
}