化为前缀和相减。考虑每一位的贡献。则需要快速查询之前有几个数和当前数的差在第k位上为1。显然其与更高位是无关的。于是用BIT维护后k位的数的出现次数，瞎算一算即可。
// luogu-judger-enable-o2 #include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 100010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n,a[N],tree[20][1<<20|1],ans; void ins(int p,int k){k++;while (k<=(1<<20)) tree[p][k]^=1,k+=k&-k;} int query(int p,int k){k++;int s=0;while (k) s^=tree[p][k],k-=k&-k;return s;} int main() { #ifndef ONLINE_JUDGEfreopen("bzoj4888.in","r",stdin);freopen("bzoj4888.out","w",stdout);const char LL[]="%I64d\n"; #elseconst char LL[]="%lld\n"; #endifn=read();for (int i=1;i<=n;i++) a[i]=a[i-1]+read();for (int i=0;i<20;i++) ins(i,0);for (int i=1;i<=n;i++)for (int j=0;j<20;j++){int inf=(1<<j+1)-1,x=a[i]&inf,r=x^(1<<j),l=x+1&inf;if ((l<=r?query(j,r)-query(j,l-1):query(j,r)+query(j,inf)-query(j,l-1))+2&1) ans^=1<<j;ins(j,x);}cout<<ans;return 0; }