传送门

对于每个二进制位考虑有多少区间和这一位上为1

从前往后扫每个前缀和,如果当前这个前缀和某一个二进制位上为1,因为区间和由这个前缀和减去前面的前缀和得来,如果减去了这一位为0的前缀和,那么 减去的前缀和的 比这一位更小的位 组成的数 要小于等于 当前前缀和 比这一位更小的位 组成的数,区间和的这一位才为1,这样子减是不会产生借位的;反之,如果减去了这一位为1的前缀和,那么 减去的前缀和的 比这一位更小的位 组成的数 要大于 当前前缀和 比这一位更小的位 组成的数,产生借位,减出来这一位才为1;如果当前这个前缀和某一个二进制位上为0就反过来

我 打 字 带 空 格

要统计在某个区间内的数的个数,用树状数组救星了

#include<bits/stdc++.h>

#define il inline

#define re register

#define LL long long

#define db double

#define ldb long double

#define eps (1e-7)

using namespace std;

const int N=300000+10;

const LL mod=20021101;

il LL rd()

{

    LL x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

LL m,g[N];

struct BIT

{

  int m,c[(1<<20)+10];

  il void init(int mm){m=mm,memset(c,0,sizeof(c));}

  il void add(int x,int y){++x;while(x<=m) c[x]+=y,x+=x&(-x);}

  il int pre(int x){++x;int an=0;while(x>=1) an+=c[x],x-=x&(-x);return an;}

  il int sum(int l,int r){return pre(r)-pre(l-1);}

}a[2];

int main()

{

  m=rd();

  for(int i=1;i<=m;i++) g[i]=g[i-1]+rd();int a2=0;

  a[0].init(g[m]+1),a[1].init(g[m]+1);

  for(int j=0;j<20;j++)

    {

      if((1<<j)>g[m]) break;

      int cn=0,ma=(1<<j)-1;

      for(int i=0;i<=m;i++)

        {

          int x=g[i]&ma,y=(g[i]>>j)&1;

          cn+=a[y^1].sum(0,x)+a[y].sum(x+1,ma);

          a[y].add(x,1);

        }

      a2^=(cn&1)<<j;

      for(int i=0;i<=m;i++)

        {

          int x=g[i]&ma,y=(g[i]>>j)&1;

          a[y].add(x,-1);

        }

    }

  printf("%d\n",a2);

  return 0;

}