一般这种位运算的题都要把每一位拆开来看，因为位运算每个位的结果这和这一位的数有关。
这样我们用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呢？？
答案是利用权值树状数组。
考虑到 $ \sum 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] $ 大。
这样就很好用权值树状数组维护了。。。。
#include
#include #include #include #define ll long long #define max(a,b) (a)>(b)?(a):(b) using namespace std; const int maxn = 1e6 + 4;inline int read() { char ch = getchar(); int f = 1 , x = 0; while(ch > '9' || ch < '0') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); } return x * f;}ll s[maxn],a[maxn];ll f[2][maxn],n,m,ans=0,now,cnt=0,tmp;bool flag;ll maxx;inline int lowbit(int x){return x & (-x);}inline void update(ll x,ll y) { for(; x<=1000000; x+=lowbit(x)) f[y][x]++;}inline ll query(ll x,ll y) { ll ansd = 0; for(; x; x-=lowbit(x)) ansd += f[y][x]; return ansd;}int main() { n = read(); for(ll i=1; i<=n; i++){ s[i] = read(); s[i] += s[i - 1]; maxx = max(maxx , 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<