TIOJ-1870

發表於 更新於 Disqus：

現在我要給你一個長度為$n$的數列，每一項初始值為$a_i$，$q$筆操作每筆操作有兩種。

一，給你L, R，請算出 [L,R] 的總和。
二，給你L, R, X，請把 [L,R] 中的所有數字都 XOR X。

$n\le 10^5, q\le 50000, a_i\le 10^6$

如果維護一顆線段樹，區間xor沒辦法直接地得出她對答案的影響(所以無法用懶標)。
但如果對於每個bit都維護一個線段樹呢?每顆線段樹都會只存01，而xor操作會變成區間反轉!
所以維護$\log a_i$科線段樹就好了。
複雜度$\mathcal{O}(N\log a_i\log N+Q\log a_i\log N)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*--------------------------------------------------------------------------------------*/

const int N = 1e5 + 25;
struct segtree {
	int arr[N << 1], tag[N], n;
	void init(int _n) { n = _n; }
	void upd(int p, int h) {
		arr[p] = (1 << h) - arr[p];
		 if(p < n)
			tag[p] ^= 1;
	}
	void push(int p) {
		for(int h = __lg(p); ~h; h--) {
			int i = p >> h;
			if(!tag[i >> 1])
				continue;
			upd(i, h);
			upd(i ^ 1, h);
			tag[i >> 1] = 0;
		}
	}
	void pull(int p) {
		for(int h = 1; p > 1; p >>= 1, h++) {
			arr[p >> 1] = arr[p] + arr[p ^ 1];
			if(tag[p >> 1])
				arr[p >> 1] = (1 << h) - arr[p >> 1];
		}
	}
	void edt(int l, int r) {
		int tl = l, tr = r, h = 0;
		push(tl + n); push(tr + n - 1);
		for(l += n, r += n; l < r; l >>= 1, r >>= 1, h++) {
			if(l & 1)
				upd(l++, h);
			if(r & 1)
				upd(--r, h);
		}
		pull(tl + n); pull(tr + n - 1);
	}
	int que(int l, int r) {
		int res = 0;
		push(l + n); push(r + n - 1);
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1)
				res += arr[l++];
			if(r & 1)
				res += arr[--r];
		}
		return res;
	}
} tree[20];

signed main() { EmiliaMyWife
	int n;
	cin >> n;
	for(int j = 0; j < 20; j++)
		tree[j].init(n);
	for(int i = 0, x; i < n; i++) {
		cin >> x;
		for(int j = 0; j < 20; j++)
			if(x >> j & 1)
				tree[j].edt(i, i + 1);
	}
	int q;
	cin >> q;
	while(q--) {
		int t;
		cin >> t;
		if(t == 1) {
			int l, r;
			cin >> l >> r;
			ll res = 0;
			for(int i = 0; i < 20; i++)
				res += ll(tree[i].que(l - 1, r)) << i;
			cout << res << '\n';
		}
		else {
			int l, r, x;
			cin >> l >> r >> x;
			for(int i = 0; i < 20; i++)
				if(x >> i & 1)
					tree[i].edt(l - 1, r);
		}
	}
}