eJOI2019 Problem A. XORanges 题解

问题描述

给定一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$，支持两种操作：

1. 将 $a_i$ 修改为 $j$
2. 查询区间 $[l, u]$ 内所有子区间的异或和的异或和

换句话说，对于询问 $[l, u]$，需要计算：

$$\bigoplus_{l \le x \le y \le u} \left( \bigoplus_{k=x}^y a_k \right) $$

其中 $\oplus$ 表示按位异或运算。

核心观察

1. 异或运算的性质

• 交换律、结合律
• 自反性：$x \oplus x = 0$
• 每个元素的贡献次数与其在表达式中出现的次数有关

2. 子区间计数

对于区间 $[l, u]$，考虑元素 $a_i$（其中 $l \le i \le u$）：

• 有多少个子区间包含 $a_i$？
• 设 $i$ 在区间 $[l, u]$ 中的位置：从左边数第 $(i-l+1)$ 个，从右边数第 $(u-i+1)$ 个
• 包含 $a_i$ 的子区间数量 = $(i-l+1) \times (u-i+1)$

3. 贡献的奇偶性

关键性质：

• 在异或运算中，一个元素出现奇数次才有贡献，出现偶数次则抵消为 $0$
• 因此，只有包含次数为奇数的元素才对最终结果有贡献

所以我们需要判断：对于每个 $a_i$，$(i-l+1) \times (u-i+1)$ 是否为奇数。

4. 奇偶性分析

$(i-l+1) \times (u-i+1)$ 为奇数 ⟺ 两个因子都是奇数

即：

• $(i-l+1)$ 是奇数
• $(u-i+1)$ 是奇数

这意味着：

• $i-l+1 \equiv 1 \pmod{2}$ ⇒ $i-l \equiv 0 \pmod{2}$ ⇒ $i$ 和 $l$ 同奇偶性
• $u-i+1 \equiv 1 \pmod{2}$ ⇒ $u-i \equiv 0 \pmod{2}$ ⇒ $i$ 和 $u$ 同奇偶性

因此，$i$ 必须与 $l$ 和 $u$ 都同奇偶性，也就是说：$l, u, i$ 的奇偶性必须相同。

5. 重要结论

对于询问 $[l, u]$：

• 只有当 $i$ 满足 $i \equiv l \pmod{2}$ 且 $i \equiv u \pmod{2}$ 时，$a_i$ 才对答案有贡献
• 由于 $i$ 必须同时与 $l$ 和 $u$ 同奇偶，实际上要求 $l$ 和 $u$ 同奇偶性
• 如果 $l$ 和 $u$ 奇偶性不同，则没有元素满足条件，答案为 $0$

当 $l$ 和 $u$ 同奇偶性时，满足条件的 $i$ 构成一个等差数列：$i = l, l+2, l+4, \dots, u$

问题转化

对于询问 $[l, u]$：

1. 如果 $(l+u)$ 是奇数（即 $l$ 和 $u$ 奇偶性不同），答案为 $0$
2. 否则，答案为：$$\bigoplus_{k=0}^{\frac{u-l}{2}} a_{l + 2k}$$ 也就是所有下标与 $l$（或 $u$）同奇偶性的元素的异或和

数据结构设计

问题转化为：

• 维护两个序列：
  • 奇数下标序列：$a_1, a_3, a_5, \dots$
  • 偶数下标序列：$a_2, a_4, a_6, \dots$
• 支持：
  1. 单点修改（同时影响奇偶性对应的序列）
  2. 区间查询：求某个奇偶性序列中一段的异或和

这可以用两个树状数组或两个线段树分别维护奇数下标和偶数下标的异或前缀和。

算法步骤

预处理

1. 构建两个树状数组：

   • BIT_odd：维护所有奇数下标 $i$（$i \bmod 2 = 1$）的异或前缀和
   • BIT_even：维护所有偶数下标 $i$（$i \bmod 2 = 0$）的异或前缀和

2. 初始化时，根据每个下标的奇偶性插入到对应的树状数组中。

查询操作 2 l u

1. 如果 $(l + u)$ 是奇数：输出 $0$

2. 否则，设起始下标为 $l$：

   • 如果 $l$ 是奇数：使用 BIT_odd 查询区间 $[l, u]$ 的异或和
   • 如果 $l$ 是偶数：使用 BIT_even 查询区间 $[l, u]$ 的异或和

   注意：树状数组通常维护前缀和，区间 $[l, u]$ 的异或和 = 前缀和$[u] \oplus$ 前缀和$[l-1]$

修改操作 1 i j

1. 获取原值 $a_i$（需要记录原数组）
2. 根据 $i$ 的奇偶性：
   • 如果是奇数：在 BIT_odd 中更新位置 $i$，先异或 $a_i$（删除旧值），再异或 $j$（添加新值）
   • 如果是偶数：在 BIT_even 中类似操作
3. 更新 $a_i = j$

时间复杂度

• 预处理：$O(n)$
• 每次操作：$O(\log n)$
• 总复杂度：$O((n+q) \log n)$，完全满足 $n, q \le 2\times 10^5$

空间复杂度

• $O(n)$

完整 C++ 实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

class BIT {
private:
    vector<int> tree;
    int n;
    
public:
    BIT(int size) {
        n = size;
        tree.resize(n + 2, 0);
    }
    
    void update(int idx, int val) {
        // 异或更新
        for (; idx <= n; idx += idx & -idx) {
            tree[idx] ^= val;
        }
    }
    
    int query(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) {
            res ^= tree[idx];
        }
        return res;
    }
    
    int range_query(int l, int r) {
        if (l > r) return 0;
        return query(r) ^ query(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    vector<int> a(n + 1);
    
    // 两个树状数组，分别维护奇数下标和偶数下标的异或前缀和
    BIT bit_odd(n), bit_even(n);
    
    // 读入初始数组并初始化树状数组
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i % 2 == 1) {
            bit_odd.update(i, a[i]);
        } else {
            bit_even.update(i, a[i]);
        }
    }
    
    while (q--) {
        int op;
        cin >> op;
        
        if (op == 1) {
            // 修改操作
            int i, j;
            cin >> i >> j;
            
            // 根据奇偶性从对应的树状数组中删除旧值
            if (i % 2 == 1) {
                bit_odd.update(i, a[i]);  // 异或旧值相当于删除
                bit_odd.update(i, j);     // 异或新值相当于添加
            } else {
                bit_even.update(i, a[i]);
                bit_even.update(i, j);
            }
            
            // 更新数组
            a[i] = j;
            
        } else {
            // 查询操作
            int l, u;
            cin >> l >> u;
            
            // 如果l和u奇偶性不同，答案为0
            if ((l + u) % 2 == 1) {
                cout << 0 << '\n';
                continue;
            }
            
            // l和u同奇偶性
            int ans;
            if (l % 2 == 1) {
                // 奇数下标序列
                // 计算在[l, u]区间内，且下标为奇数的元素的异或和
                // 这些元素的下标为：l, l+2, l+4, ..., u
                // 我们需要在bit_odd中查询这些位置
                ans = bit_odd.range_query(l, u);
            } else {
                // 偶数下标序列
                ans = bit_even.range_query(l, u);
            }
            
            cout << ans << '\n';
        }
    }
    
    return 0;
}

样例验证

样例1

输入：
3 3
1 2 3
2 1 3
1 1 3
2 1 3

输出：
2
0

过程：

1. 初始：bit_odd 维护 [1, 3]，bit_even 维护 [2]
2. 第一次查询 [1, 3]：l=1(奇)，查询奇数下标 1,3 的异或：1^3=2
3. 修改 a[1]=3：更新 bit_odd
4. 第二次查询 [1, 3]：奇数下标 1,3 的异或：3^3=0

样例2

输入：
5 6
1 2 3 4 5
2 1 3
1 1 3
2 1 5
2 4 4
1 1 1
2 4 4

输出：
2
5
4
4

正确性证明

1. 贡献奇偶性：通过分析 $(i-l+1) \times (u-i+1)$ 的奇偶性，证明了只有当 $i$ 与 $l$、$u$ 都同奇偶时，$a_i$ 才出现奇数次。
2. 完备性：所有满足条件的 $i$ 构成等差数列 $l, l+2, \dots, u$，恰好是需要计算异或和的元素。
3. 边界处理：树状数组正确处理了区间查询和单点更新。

扩展思考

1. 如果要求所有子区间的和（而不是异或和），问题会复杂得多，因为需要处理进位。
2. 如果支持区间修改（如区间异或），则需要使用线段树维护懒标记。
3. 本题的数学推导是关键，将看似 $O(n^2)$ 的问题转化为 $O(\log n)$ 的查询。

总结

本题巧妙利用异或运算的性质和组合数学的奇偶性分析，将复杂问题简化为两个简单序列的维护。核心洞察是发现只有下标与区间端点同奇偶的元素才有贡献，从而可以用高效的数据结构解决。