fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9; 
  8. const ll LINF = 1e18;  
  9.  
  10. // Bài này các em có thể xử lí độc lập theo từng bit
  11.  
  12. // ***Đối với truy vấn get***: 
  13. // 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] 
  14. // thì giá trị mà bit thứ i đóng góp vào trong đáp án là: 2^i * cnt(i, l, r) 
  15. // với cnt(i, l, r) là số lượng phần tử trong đoạn [l, r] sao cho bit thứ i của nó = 1
  16.  
  17. // ***Đối với truy vấn update***: 
  18. // Xét đoạn [l, r] bất kì, giả sử ta cần xor mỗi phần tử với x
  19. // 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])
  20. // Giả sử bit thứ i của x bằng 1: 
  21. // - Đối với những phần tử thuộc [l, r] sao cho bit thứ i = 0, thì bit thứ i của bọn nó bây giờ sẽ bằng 1 | 
  22. // - Đối với những phần tử thuộc [l, r] sao cho bit thứ i = 1, thì bit thứ i của bọn nó bây giờ sẽ bằng 0 | (tính chất của phép xor)
  23.  
  24. // Nên từ đây mấy em sẽ có 20 cây Segment Tree, seg[i] sẽ quản lí những vị trí pos sao cho bit thứ i của a[pos] bằng 1
  25.  
  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 seg[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 bit = 0; bit <= 19; bit++) {
  94. 		seg[bit] = segTree(n);   
  95. 		for (int i = 1; i <= n; i++) {
  96. 			if ((a[i] >> bit) & 1) seg[bit].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 bit = 0; bit <= 19; bit++) {
  109. 				if ((x >> bit) & 1) seg[bit].update(1, 1, n, l, r); 
  110. 			} 
  111. 		}
  112. 		else {
  113. 			ll ans = 0;  
  114. 			for (int bit = 0; bit <= 19; bit++) {
  115. 				ans += (1ll << bit) * seg[bit].get(1, 1, n, l, r); 
  116. 			}
  117. 			cout << ans << '\n';
  118. 		}
  119. 	}
  120. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
6
4 7 4 0 7 3
5
2 2 3 8
1 1 5
2 3 5 1
2 4 5 6
1 2 3
stdout
copy 
38
28
https://ideone.com/LBKkLc
language:
C++14 (gcc 8.3)
created:
1 year 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!