fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9; 
  9. const ll LINF = 1e18;  
  10.  
  11. // Ta có thể xử lí độc lập theo từng bit
  12.  
  13. // ***Đối với truy vấn get***: 
  14. // Xét đoạn [l, r] bất kì, giả sử ta cần tính a[l] + a[l + 1] + a[l + 2] + ... + a[r] 
  15. // thì giá trị mà bit thứ k đóng góp vào trong đáp án sẽ là 2^k * cnt(k, l, r) 
  16. // với cnt(k, l, r) là số lượng phần tử trong đoạn [l, r] sao cho bit thứ k của nó = 1
  17.  
  18. // ***Đối với truy vấn update***: 
  19. // Xét đoạn [l, r] bất kì, giả sử ta cần xor mỗi phần tử với x
  20. // Ta chỉ cần xét những bit 1 của x (những bit bằng 0 không làm ảnh hưởng đến giá trị của đoạn [l, r])
  21. // Giả sử bit thứ k của x bằng 1: 
  22. // - Đối với những phần tử thuộc [l, r] sao cho bit thứ k = 0, thì bit thứ k của chúng sẽ bị thay đổi thành 1  
  23. // - Đối với những phần tử thuộc [l, r] sao cho bit thứ k = 1, thì bit thứ k của chúng sẽ bị thay đổi thành 0 
  24.  
  25. // Nên từ đây ta có 20 cây Segment Tree, tree[k] sẽ quản lí những vị trí i sao cho bit thứ k của a[i] bằng 1
  26. const int N = 1e5 + 5; 
  27.  
  28. int n, q;  
  29. int a[N]; 
  30.  
  31. struct SegTree {
  32. 	int n;  
  33. 	vector<int> seg, lazy;  
  34.  
  35. 	SegTree() {}
  36.  
  37. 	SegTree(int n): n(n) {
  38. 		seg.resize(4 * n + 1, 0); 
  39. 		lazy.resize(4 * n + 1, 0); 
  40. 	}
  41.  
  42. 	void push(int id, int l, int r) {
  43. 		if (lazy[id] == 1) {
  44. 			int mid = (l + r) >> 1; 
  45.  
  46. 			seg[id * 2] = (mid - l + 1) - seg[id * 2]; 
  47. 			lazy[id * 2] ^= lazy[id]; 
  48.  
  49. 			seg[id * 2 + 1] = (r - mid) - seg[id * 2 + 1]; 
  50. 			lazy[id * 2 + 1] ^= lazy[id]; 
  51.  
  52. 			lazy[id] = 0;  
  53. 		}
  54. 	}
  55.  
  56. 	void update(int id, int l, int r, int u, int v) {
  57. 		if (l > v || r < u) return; 
  58.  
  59. 		if (u <= l && r <= v) {
  60. 			seg[id] = (r - l + 1) - seg[id]; 
  61. 			lazy[id] ^= 1; 
  62. 			return; 
  63. 		}
  64.  
  65. 		push(id, l, r);  
  66.  
  67. 		int mid = (l + r) >> 1;  
  68. 		update(id * 2, l, mid, u, v); 
  69. 		update(id * 2 + 1, mid + 1, r, u, v); 
  70.  
  71. 		seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  72. 	}
  73.  
  74. 	int get(int id, int l, int r, int u, int v) {
  75. 		if (l > v || r < u) return 0;   
  76.  
  77. 		if (u <= l && r <= v) return seg[id]; 
  78.  
  79. 		push(id, l, r); 
  80.  
  81. 		int mid = (l + r) >> 1; 
  82. 		return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v); 
  83. 	}
  84. }; 
  85.  
  86. SegTree tree[20];  
  87.  
  88. int main() {
  89. 	ios::sync_with_stdio(0); cin.tie(0);  	
  90. 	cin >> n; 
  91. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  92.  
  93. 	for (int k = 0; k <= 19; k++) {
  94. 		tree[k] = SegTree(n);   
  95. 		for (int i = 1; i <= n; i++) {
  96. 			if ((a[i] >> k) & 1) tree[k].update(1, 1, n, i, i); 
  97. 		}
  98. 	}
  99.  
  100. 	cin >> q; 
  101.  
  102. 	while (q--) {
  103. 		int type, l, r; 
  104. 		cin >> type >> l >> r; 
  105.  
  106. 		if (type == 2) {
  107. 			int x; cin >> x;  
  108. 			for (int k = 0; k <= 19; k++) {
  109. 				if ((x >> k) & 1) tree[k].update(1, 1, n, l, r); 
  110. 			} 
  111. 		}
  112. 		else {
  113. 			ll ans = 0;  
  114. 			for (int k = 0; k <= 19; k++) {
  115. 				ans += (1ll << k) * tree[k].get(1, 1, n, l, r); 
  116. 			}
  117. 			cout << ans << '\n';
  118. 		}
  119. 	}
  120. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3
stdout 
26
22
0
34
11
https://ideone.com/RqLoby
language:
C++14 (gcc 8.3)
created:
37 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!