题目链接

题意分析

题意精简一下就是

求所有连续区间和的异或和

由于涉加到计算区间和 所以我们先跑一个前缀和

然后 由于涉及到了位运算 我们很自然地联想到了拆位

对于当前我们枚举到了第\(k\)位

我们到了第\(i\)个数\(s_i\)

如果\(s_i\)当前这一位是\(1\)

1.存在\(s_j(j<i)\)当前这一位是\(0\) 并且\(0\)到\(k-1\)位的数值\(≤i\)

那么就可以产生\(2^k\)的贡献

2.存在\(s_j(j<i)\)当前这一位是\(1\) 并且\(0\)到\(k-1\)位的数值\(>i\)

那么也可以产生\(2^k\)的贡献(可以手捯饬一下)

同理 如果\(s_i\)当前这一位是\(0\)

1.存在\(s_j(j<i)\)当前这一位是\(1\) 并且\(0\)到\(k-1\)位的数值\(≤i\)

那么就可以产生\(2^k\)的贡献

2.存在\(s_j(j<i)\)当前这一位是\(0\) 并且\(0\)到\(k-1\)位的数值\(>i\)

那么也可以产生\(2^k\)的贡献(可以手捯饬一下)

我们可以使用权值树状数组维护当前\(0\)到\(k-1\)位的数值

同时要注意\(0\)也要加进去

CODE:

/*-------------OI使我快乐-------------*/
int n,ans;
int num[M],sum[M],tre[M][2];
IL void add(int x,int knd)
{++x;for(;x<=maxn;x+=x&-x) tre[x][knd]++;}
IL int qury(int x,int knd)
{++x;int res=0;for(;x;x-=x&-x) res+=tre[x][knd];return res;}
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(n);
    for(R int i=1;i<=n;++i) read(num[i]),sum[i]=sum[i-1]+num[i];
    for(R int j=0;j<=25;++j)
    {
        if((1<<j)>maxn) break;
        memset(tre,0,sizeof tre);int cnt=0;
        add(0,0);
        for(R int i=1;i<=n;++i)
        {
            int now=sum[i]&((1<<j)-1),flag=((sum[i]&(1<<j))>>j);
            cnt=(cnt+qury(now,flag^1))&1;
            cnt=(cnt+qury(maxn,flag)-qury(now,flag))&1;
            add(now,flag);
        }
        if(cnt) ans+=(1<<j);
    }
    printf("%d\n",ans);
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

HEOI 2019 RP++

P3760 [TJOI2017]异或和

原文：https://www.cnblogs.com/LovToLZX/p/10623514.html