BZOJ4888 Tjoi2017异或和（树状数组）

　　化为前缀和相减。考虑每一位的贡献。则需要快速查询之前有几个数和当前数的差在第k位上为1。显然其与更高位是无关的。于是用BIT维护后k位的数的出现次数，瞎算一算即可。

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,a[N],tree[][<<|],ans;

void ins(int p,int k){k++;while (k<=(<<)) tree[p][k]^=,k+=k&-k;}

int query(int p,int k){k++;int s=;while (k) s^=tree[p][k],k-=k&-k;return s;}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4888.in","r",stdin);

    freopen("bzoj4888.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=;i<=n;i++) a[i]=a[i-]+read();

    for (int i=;i<;i++) ins(i,);

    for (int i=;i<=n;i++)

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

        {

            int inf=(<<j+)-,x=a[i]&inf,r=x^(<<j),l=x+&inf;

            if ((l<=r?query(j,r)-query(j,l-):query(j,r)+query(j,inf)-query(j,l-))+&) ans^=<<j;

            ins(j,x);

        }

    cout<<ans;

    return ;

}