题目理解

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，设 $$S_{i,j} = a_i + a_{i+1} + \dots + a_j$$ 为一段连续子数组的和。

我们需要计算：

$$\text{Ans} = S_{1,1} \oplus S_{1,2} \oplus \dots \oplus S_{1,n} \oplus S_{2,2} \oplus \dots \oplus S_{n,n} $$

即所有连续和的异或值。

---

核心思路

1. 异或运算的性质

异或运算具有按位独立性，即：

$$\text{Ans} = \sum_{k=0}^{\text{maxbit}} \left( \text{第k位为1的连续和个数} \bmod 2 \right) \times 2^k $$

因此我们可以按位考虑，对每一位 $k$，统计有多少个连续和在该位为 $1$，如果是奇数个，最终答案的这一位就是 $1$。

---

2. 转化为前缀和问题

设前缀和 $P_i = a_1 + a_2 + \dots + a_i$，$P_0 = 0$。

则连续和 $S_{i,j} = P_j - P_i$（其中 $i < j$）。

我们要统计对于第 $k$ 位，有多少对 $(i,j)$ 满足：

$$(P_j - P_i) \ \& \ (1 \ll k) \neq 0$$

即 $P_j - P_i$ 的第 $k$ 位为 $1$。

---

3. 按位统计的方法

对于第 $k$ 位，设 $mask = (1 \ll k) - 1$（低 $k$ 位全为 $1$）。

将 $P_j$ 拆分为高位 $c_j$ 和低位 $A_j$：

• $c_j = P_j \ \&\ (1 \ll k)$（第 $k$ 位的值）
• $A_j = P_j \ \&\ mask$（低 $k$ 位的值）

那么 $P_j - P_i$ 的第 $k$ 位为 $1$ 的条件，取决于 $c_j, c_i$ 和 $A_j, A_i$ 的关系。

---

情况分析：

1. $c_j = c_i$（高位相同）

   • 当 $A_j < A_i$ 时，$P_j - P_i$ 的第 $k$ 位为 $1$
   • 因为借位导致高位变化

2. $c_j \neq c_i$（高位不同）

   • 当 $A_j \ge A_i$ 时，$P_j - P_i$ 的第 $k$ 位为 $1$
   • 直接相减高位就为 $1$

---

4. 使用树状数组维护

我们使用两个树状数组：

• $T[0]$：记录 $c_i = 0$ 的前缀和的低位 $A_i$ 的分布
• $T[1]$：记录 $c_i = 1$ 的前缀和的低位 $A_i$ 的分布

对于每个 $P_j$，根据其 $c_j$ 的值，查询对应的树状数组来统计满足条件的 $P_i$ 的数量。

---

代码解析

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int M = 1e6 + 5, N = 1e5 + 5;
#define LB(x) (x&-x)

struct BIT {
    LL t[M];
    inline void Clear() {
        memset(t, 0, sizeof(t));
    }
    inline void Upd(int x) {
        for (int i = x + 1; i < M; i += LB(i))
            t[i]++;
    }
    inline LL Qry(int x) {
        LL S = 0;
        for (int i = x + 1; i; i -= LB(i))
            S += t[i];
        return S;
    }
} T[2];  // 两个树状数组，分别对应c=0和c=1的情况

int n;
LL S[N], Ans;  // S是前缀和数组

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    
    // 计算前缀和
    for (int i = 1; i <= n; i++) {
        cin >> S[i];
        S[i] += S[i - 1];
    }
    
    // 按位考虑，最多20位(因为sum <= 1e6 < 2^20)
    for (int i = 0; i <= 20; i++) {
        T[0].Clear(), T[1].Clear();
        int k = 0;  // 统计第i位为1的连续和数量的奇偶性
        T[0].Upd(0);  // 加入P0 = 0
        
        for (int j = 1; j <= n; j++) {
            int c = S[j] & (1 << i);        // 第i位的值
            int A = S[j] & ((1 << i) - 1);  // 低i位的值
            
            if (c) {
                // 当c_j = 1时：
                // 1. c_i = 1 且 A_j < A_i 的情况
                // 2. c_i = 0 且 A_j >= A_i 的情况
                k ^= (T[0].Qry(A) + T[1].Qry(M - 5) - T[1].Qry(A)) % 2;
            } else {
                // 当c_j = 0时：
                // 1. c_i = 0 且 A_j < A_i 的情况  
                // 2. c_i = 1 且 A_j >= A_i 的情况
                k ^= (T[1].Qry(A) + T[0].Qry(M - 5) - T[0].Qry(A)) % 2;
            }
            
            T[c > 0].Upd(A);  // 将当前前缀和加入对应的树状数组
        }
        
        if (k)  // 如果第i位为1的连续和个数是奇数
            Ans += (1 << i);
    }
    
    cout << Ans << endl;
    return 0;
}

---

关键点说明

1. 树状数组下标处理

代码中 Upd(x) 和 Qry(x) 使用 x+1 是为了避免 $x=0$ 时的死循环。

2. 查询逻辑

• T[0].Qry(A)：$c_i=0$ 且 $A_i \le A$ 的数量
• T[1].Qry(M-5) - T[1].Qry(A)：$c_i=1$ 且 $A_i > A$ 的数量

3. 奇偶性统计

由于我们只关心数量的奇偶性，所以用 % 2 和 ^= 来维护。

---

复杂度分析

• 时间复杂度：$O(n \log n \log MAX)$，其中 $MAX$ 是值域
• 空间复杂度：$O(MAX)$

这种方法巧妙地利用了按位独立和树状数组维护低位比较的思想，避免了直接枚举所有连续和的高复杂度。