题解 P3760 【[TJOI2017]异或和】
为啥有没题解。。。。蒟蒻来水一水吧。。。
一般这种位运算的题都要把每一位拆开来看，因为位运算每个位的结果这和这一位的数有关。
这样我们用s[i]表示a的前缀和，即a[1]+a[2]+....a[i]，然后我们从这些数二进制最右位（2^0）开始，按照每一位对答案的贡献来计算。
假设我们现在算到最右位（2^0）,并且位于第i个数，我们想要知道以i结尾的连续和对答案的贡献，只需要知道有多少s[i]-s[j]（0<=j<i）的2^0位是1。 （设s[0]=0）
如果这个数是奇数，就说明异或了1奇数次，也就相当于异或了1，我们只需要把记录这一位总的异或贡献的变量cnt异或1即可；
如果是偶数就不用管了，对答案没有贡献。
对于数的每一位如果最后cnt=1的话，就说明在这一位所有连续和的异或和为1，我们就需要把答案加上(1<<(这个位数））。
那如何快速计算有多少个s[i]-s[j]的二进制第k位是否为1呢？？
答案是利用权值树状数组。
考虑到Σa 最大才有1000000，我们构造两棵权值树状数组，一棵记录当前位为1的，另一棵记录为0的。
如果当前扫描到的s[i]的二进制第k位为1，那么对这一位的答案有贡献的只有那些第k位为1且第k位向右的数比s[i]第k位向右的数大的或者第k位为0且第k位向右的数不比s[i]第k位向右的数大的。（可能有点拗口，，都怪我语文学的不好）
为什么呢？
因为如果第k位都为1的话，那么只有后面那些位的和大于s[i]的数，s[i]减去它之后第k位才能出现1（因为s[i]比它小的话需要向更高位借数，就和小学学的横式减法差不多），从而对答案作出贡献；
如果第k位为0的话，如果后面再比s[i]大的话，s[i]第k位的1就需要借给低一位的了，所以后面必须不比s[i]大。
这样就很好用权值树状数组维护了。。。。
code:
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
ll s[100005],a[100005];
ll f[2][1000005],n,m,ans=0,now,cnt=0,tmp;
bool flag;
ll maxn;
inline void read(ll&x){
x=0; char ch=getchar();
while(!isdigit(ch)) ch=getchar();
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
}
inline void update(ll x,ll y){
for(;x<=1000000;x+=x&-x) f[y][x]++;
}
inline ll query(ll x,ll y){
ll ansd=0;
for(;x;x-=x&-x) ansd+=f[y][x];
return ansd;
}
int main(){
read(n);
for(ll i=1;i<=n;i++) read(s[i]),s[i]+=s[i-1],maxn=max(maxn,s[i]);
for(ll i=0;i<=20;i++){
if((1<<i)>maxn) break;
memset(f,0,sizeof(f));
flag=0,cnt=0;
update(1,0);
for(ll j=1;j<=n;j++){
tmp=s[j]&(1<<i);
if(tmp) 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%2) cnt^=1;
update(a[j]+1,(tmp>0?1:0));
a[j]|=tmp;
}
if(cnt) ans+=(1<<i);
}
cout<<ans;
return 0;
}