C++11(clang++ 3.9) 解法, 执行用时: 116ms, 内存消耗: 8684K, 提交时间: 2019-12-20 19:28:59

#include <cstdio>
#include <cctype>
#include <cstring>
#define rr register
using namespace std;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans; 
}
int n,s[100001],lim,ans;
struct szsz{
    int c[1000101];
	inline void add(int x,int y){for (++x;x<=lim+1;x+=-x&x) c[x]+=y;}
    inline signed answ(int x){rr int ans=0; for (++x;x;x-=-x&x) ans+=c[x]; return ans;}
    inline signed aasw(int l,int r){return answ(r)-answ(l);}
}c0,c1;
signed main(){
	n=iut();
	for (rr int i=1;i<=n;++i) s[i]=s[i-1]+iut();
	for (rr int k=0;(1<<k)<=s[n];++k){
		lim=(1<<k)-1; rr int sum=0;
		for (rr int i=0;i<=n;++i){
			rr int now=s[i]&lim;
			if ((s[i]>>k)&1) sum+=c0.aasw(-1,now)+c1.aasw(now,lim),c1.add(now,1);
			    else sum+=c1.aasw(-1,now)+c0.aasw(now,lim),c0.add(now,1);
		}
		ans+=(1<<k)*(sum&1),memset(c0.c,0,sizeof(c0.c)),memset(c1.c,0,sizeof(c1.c));
	}
	return !printf("%d",ans);
}

C++14(g++5.4) 解法, 执行用时: 71ms, 内存消耗: 8676K, 提交时间: 2020-06-30 12:45:13

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,M=1e6+5;
 
inline int read(){
    int x=0; char ch=getchar();
    for(;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x;
}
 
int n,a[N],f[2][M],ans,i,now,oe; 
 
inline void update(int T,int x){
	for(;x<=i;x+=x&-x) f[T][x]^=1;
}
 
inline int query(int T,int x){
	int an=0;
	for(;x;x-=x&-x) an^=f[T][x];
	return an;
}
 
int main(){
	n=read();
	for(i=1;i<=n;i++) a[i]=read()+a[i-1];
	
	for(i=1,now=0,oe;i<=a[n];now|=i,i<<=1){
		memset(f,0,sizeof(f)),oe=0;
		
		update(0,1);
		for(int j=1,u,p;j<=n;j++){
			u=(a[j]&i)?1:0,p=(a[j]&now)+1;
			oe^=query(u^1,p)^query(u,i)^query(u,p);
			update(u,p);
		}
		
		ans+=i*oe;
	}
	
	printf("%d\n",ans);
	return 0;
}