异或和

对于位运算来说,一般都是按位维护,题目要你求所有子段和的异或和,那么我们按位处理就好了.
a[j]存的是在(1<<i)的情况下,小于第i位的sum[j]的值,然后就是讨论该位1是否发生变化了.第二题就写完了...emm

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e6+5;
int a[N],sum[2][M],s[N];
int lowbit(int x)   {  return x&(-x); }

void add(int pos,int val,int op)
{
    while(pos<=M-5)
    {
        sum[op][pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos,int op)
{
    int res=0;
    while(pos)
    {
        res+=sum[op][pos];
        pos-=lowbit(pos);
    }
    return res;
}

int main()
{
    int n,x,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   {scanf("%d",&x);s[i]+=s[i-1]+x;}
    for(int i=0;i<=20;i++)
    {
        //1位1位算.
        memset(sum,0,sizeof sum);
        add(1,1,0);
        int cnt=0,now,temp;
        for(int j=1;j<=n;j++)
        {
            temp=s[j]&(1<<i);
            if(temp)  now=query(a[j]+1,0)+query(1000000,1)-query(a[j]+1,1);
            else      now=query(a[j]+1,1)+query(1000000,0)-query(a[j]+1,0);
            if(now&1)   cnt^=1;
            add(a[j]+1,1,(temp>0?1:0));
            a[j]|=temp;
        }
        if(cnt) ans+=(1<<i);
    }
    printf("%d\n",ans);
    return 0;
}