因为答案要求所有连续段和的异或，所以考虑维护所有子段和的出现次数的奇偶性。

用 bitset 维护，记录当前所有以当前数字结尾的字段和的出现情况。

每次将前面的字段和全部左移 $a_i$ 位，然后在将 $a_i$ 翻转即可。

每次答案的 bitset 直接异或上维护的子段和即可。

时间复杂度为 $O(\frac{n \cdot \sum a_i}{w})$。

#include <bits/stdc++.h>
using namespace std;
bitset<1000005> h;
bitset<1000005> ans;
int a[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        h<<=a[i];
        h.flip(a[i]);
        ans^=h;
    }
    long long res=0;
    for(int i=1;i<=1000000;i++)
    {
        if(ans[i]) res^=i;
    }
    cout<<res;
    return 0;
}

发现数据差一点就能通过，需要卡常。

在左移和异或时，在前面数不多时浪费大量时间，所以手写 bitset，每次只用异或到当前所有子段和的最大值。

可以优化掉两倍常数，足以通过。

#include <bits/stdc++.h>
using namespace std;
#define B 1<<20
char buf[B],*S=buf,*T=buf;
inline char gc() { return S==T&&(T=(S=buf)+fread(buf,1,B,stdin),S==T)?EOF:*S++; }
inline int rd()
{
    int x=0;char ch=gc();
    while(ch<'0'||ch>'9')ch=gc();
    while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=gc();
    return x;
}
typedef unsigned long long u64;
const int L=(1000005>>6)+5;
u64 h[L],ans[L];
int main()
{
    int n=rd(),tp=0,cs=0;
    for(int i=1;i<=n;i++)
    {
        int v=rd();
        cs+=v;
        int sh=v>>6,st=v&63;
        if(!st)
        {
            for(int j=tp;j>=0;j--)h[j+sh]=h[j],sh?h[j]=0:0;
        }
        else
        {
            for(int j=tp;j>=0;j--)
            {
                h[j+sh+1]^=(h[j]>>(64-st));
                h[j+sh]=(h[j]<<st);
                if(sh)h[j]=0;
            }
        }
        tp=(cs>>6)+1;
        if(tp>=L)tp=L-1;
        h[v>>6]^=(1ULL<<(v&63));
        for(int j=0;j<=tp;j++)ans[j]^=h[j];
    }
    int res=0;
    for(int i=0;i<L;i++)
    {
        if(!ans[i])continue;
        for(int j=0;j<64;j++)
            if((ans[i]>>j)&1)res^=(i<<6|j);
    }
    cout<<res;
    return 0;
}