算法
(线段树) $O((n+q) \log n)$
由于 $a \oplus b$ 以 $0$ 为单位元并满足结合律,因此可以使用线段树来高速处理它。
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int op(int x, int y) { return x ^ y; }
int e() { return 0; }
int main() {
int n, q;
cin >> n >> q;
segtree<int, op, e> t(n);
rep(i, n) {
int a;
cin >> a;
t.set(i, a);
}
rep(qi, q) {
int type, x, y;
cin >> type >> x >> y;
--x;
if (type == 1) {
t.set(x, t.get(x) ^ y);
}
else {
int ans = t.prod(x, y);
cout << ans << '\n';
}
}
return 0;
}