题目大意

给定一个长为 $n$ 的数列 $\{a_i\}$，有如下操作

  • 询问区间 $[l, r]$ 上的和。
  • 对 $[l, r]$ 区间上每个数异或上一个数 $x$。

分析

只需注意到异或是不进位的，我们可以单独维护数列的每一位。开二十棵线段树即可。

int main() {
	int n;
	cin >> n;

	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	vector<SegmentTree<int>> tr;
	for (int k = 0; k < 20; k++) {
		tr.push_back(SegmentTree<int>(n + 1));
		vector<int> tmp(n + 1);
		for (int i = 1; i <= n; i++) {
			if ((1 << k) & a[i])
				tmp[i] = 1;
		}
		tr[k].build(tmp);
	}

	int Q;
	cin >> Q;
	while (Q--) {
		int op, l, r;
		cin >> op >> l >> r;
		if (op == 1) {
			ll ans = 0;
			for (int k = 0; k < 20; k++) {
				ans += 1ll * tr[k].query(l, r) << k;
			}
			cout << ans << "\n";
		} else {
			int x;
			cin >> x;
			for (int k = 0; k < 20; k++) {
				if (x & (1 << k)) {
					tr[k].modify(l, r, 1);
				}
			}
		}
	}
	return 0;
}