思路与算法

在模2意义下做差分：d[1]=a[1]，d[i]=a[i] xor a[i-1]。翻转 [L,R] 时，区间内部相邻两项同时变化，差分不变；只有 d[L] 与 d[R+1] 需要各异或1。用支持异或的树状数组维护差分，询问 a[i] 就查询 d[1..i] 的前缀异或。

正确性说明

任意前缀异或 d[1] xor … xor d[i] 中，相邻项会两两抵消，结果等于 a[i]。区间翻转只改变区间两端的相邻关系，因此两个端点更新与直接翻转整个区间等价。每次操作后这一差分关系保持成立，所以所有点查询都正确。

复杂度

每次更新或查询 O(log N)，总时间 O(N+M log N)，空间 O(N)。

易错点

R=N 时 R+1 在数组之外，不需要更新。连续翻转两次应恢复原值。操作2只有一个下标，不能按两个端点读取。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> bit(n + 1);
    auto flip = [&](int x) {
        for (; x <= n; x += x & -x)
            bit[x] ^= 1;
    };
    while (m--) {
        int t, l, r;
        cin >> t >> l;
        if (t == 1) {
            cin >> r;
            flip(l);
            flip(r + 1);
        } else {
            int v = 0;
            for (int i = l; i; i -= i & -i)
                v ^= bit[i];
            cout << v << '\n';
        }
    }
}