自动搬运

查看原文

来自洛谷，原作者为

	金爷爷哈哈 **

搬运于2025-08-24 21:52:25，当前版本为作者最后更新于2017-08-10 19:36:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为啥有没题解。。。。蒟蒻来水一水吧。。。

一般这种位运算的题都要把每一位拆开来看，因为位运算每个位的结果这和这一位的数有关。

这样我们用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;
}