$ color{#0066ff}{ 题目描述 }$
在加里敦中学的小明最近爱上了数学竞赛，很多数学竞赛的题都是与序列的连续和相关的。所以对于一个序列，求出它们所有的连续和来说，小明觉得十分的简单。但今天小明遇到了一个序列和的难题，这个题目不仅要求你快速的求出所有的连续和，还要快速的求出这些连续和的异或值。小明很快的就求出了所有的连续和，但是小明要考考你，在不告诉连续和的情况下，让你快速求是序列所有连续和的异或值。
(color{#0066ff}{输入格式})
第一行输入一个n,表示这序列的数序列 第二行输入n个数字a1,a2...an代表这个序列
0<=a1,a2,...an，0<=a1+a2...+an<=(10^6)
(color{#0066ff}{输出格式})
输出这个序列所有的连续和的异或值
(color{#0066ff}{输入样例})
3
1 2 3
(color{#0066ff}{输出样例})
0
(color{#0066ff}{数据范围与提示})
【样例解释】
序列1 2 3有6个连续和，它们分别是1 2 3 3 5 6，则1 xor 2 xor 3 xor 3 xor 5 xor 6 = 0
【数据范围】
对于20%的数据，1<=n<=100
对于100%的数据，1<=n <= (10^5)
(color{#0066ff}{题解})
首先，连续的和（区间和），我们不难想到前缀和
暴力的话这样就是O(n^2)的了
显然数据范围的话我们要考虑一个(O(nlogn))的做法， 肯定是优化掉内层枚举，考虑对于每一个前缀和(s_i)，快速求出它的贡献
直接求显然加减还有异或弄一起肯定不好求，但是发现一个东西，就是(s_nle10^6)，于是我们考虑拆位， 统计每一位的贡献
对于一个(s_i)，考虑那些j会使得(s_i-s_j)当前位为1
如果(s_i)当前位为1，那么一定是找比它小的且当前位为0的一减，才能出来1，当然还有比他大的（当前）一减，像减法借位一样也会出1
同理当前位为0也是这样，统计一下贡献就行
#include<bits/stdc++.h>
#define LL long long
LL read() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
template<class T> bool chkmax(T &a, const T &b) { return a < b? a = b, 1 : 0; }
template<class T> bool chkmin(T &a, const T &b) { return b < a? a = b, 1 : 0; }
const int maxn = 1e6 + 100;
struct Binary_Indexed_Tree {
protected:
int st[maxn];
int low(int x) { return x & (-x); }
int n;
public:
void set(int n) { this->n = n; }
void add(int pos) { pos++; while(pos <= n) st[pos]++, pos += low(pos); }
int query(int pos) { pos++; int re = 0LL; while(pos) re += st[pos], pos -= low(pos); return re; }
void clr() { memset(st, 0, sizeof st); }
}T[2];
int a[maxn], n, b[maxn], max, ans;
int main() {
T[0].set(1e6 + 10), T[1].set(1e6 + 10);
n = read();
for(int i = 1; i <= n; i++) a[i] = a[i - 1] + read();
max = a[n];
for(int j = 0; (1 << j) <= max; j++) {
T[0].clr(), T[1].clr();
T[0].add(0);
int num = 0;
for(int i = 1; i <= n; i++) {
int now = (a[i] >> j) & 1, tot;
if(now) tot = T[0].query(b[i]) + T[1].query(1e6) - T[1].query(b[i]);
else tot = T[1].query(b[i]) + T[0].query(1e6) - T[0].query(b[i]);
if(tot & 1) num ^= 1;
T[now].add(b[i]);
b[i] |= (now << j);
}
if(num) ans |= (1 << j);
}
printf("%d
", ans);
return 0;
}