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. const int N = 1e5 + 5; 
  11. const int Q = 1e5 + 5; 	
  12. const int B = 300;   
  13.  
  14. struct Query {
  15. 	int l, r, idx; 
  16. 	bool operator<(const Query& other) const {
  17. 		if (l / B == other.l / B) {
  18. 			return (l / B & 1) ? (r > other.r) : (r < other.r); 
  19. 		}
  20. 		return l < other.l; 
  21. 	}
  22. }; 
  23.  
  24. int n, q, k;  
  25. int a[N], pref[N]; 
  26. vector<Query> queries; 
  27.  
  28. ll cur_ans; 
  29. int cnt_pref_l[1 << 20], cnt_pref_r[1 << 20]; 
  30. ll ans[Q]; 
  31.  
  32. // Mỗi khi thêm hoặc xoá một đầu mút i ở bên trái thì ta cần đếm xem có bao nhiêu đầu mút r
  33. // sao cho pref[r] ^ pref[i - 1] = k hay pref[r] = pref[i - 1] ^ k 
  34. void addLeft(int i) {
  35. 	cnt_pref_r[pref[i]]++;  
  36. 	cnt_pref_l[pref[i - 1]]++; 
  37. 	cur_ans += cnt_pref_r[pref[i - 1] ^ k]; 
  38. }
  39.  
  40. void removeLeft(int i) {
  41. 	cur_ans -= cnt_pref_r[pref[i - 1] ^ k]; 
  42. 	cnt_pref_l[pref[i - 1]]--; 
  43. 	cnt_pref_r[pref[i]]--; 
  44. }
  45.  
  46. // Mỗi khi thêm hoặc xoá một đầu mút i ở bên phải thì ta cần đếm xem có bao nhiêu đầu mút l 
  47. // sao cho pref[i] ^ pref[l - 1] = k hay pref[l - 1] = pref[i] ^ k 
  48. void addRight(int i) {
  49. 	cnt_pref_l[pref[i - 1]]++; 
  50. 	cnt_pref_r[pref[i]]++;
  51. 	cur_ans += cnt_pref_l[pref[i] ^ k]; 
  52. }
  53.  
  54. void removeRight(int i) {
  55. 	cur_ans -= cnt_pref_l[pref[i] ^ k]; 
  56. 	cnt_pref_r[pref[i]]--;
  57. 	cnt_pref_l[pref[i - 1]]--; 
  58. }
  59.  
  60. int main() {
  61. 	ios::sync_with_stdio(0); cin.tie(0);  	
  62. 	cin >> n >> q >> k; 
  63. 	for (int i = 1; i <= n; i++) {
  64. 		cin >> a[i]; 
  65. 		pref[i] = pref[i - 1] ^ a[i]; 
  66. 	}
  67.  
  68. 	for (int i = 0; i < q; i++) {
  69. 		int l, r; 
  70. 		cin >> l >> r; 
  71. 		queries.push_back({l, r, i}); 
  72. 	}
  73.  
  74. 	sort(queries.begin(), queries.end()); 
  75.  
  76. 	cur_ans = 0;   
  77. 	int cur_l = 1, cur_r = 0;  
  78.  
  79. 	for (Query q : queries) {
  80. 		while (cur_l > q.l) {
  81. 			cur_l--; 
  82. 			addLeft(cur_l); 
  83. 		}
  84.  
  85. 		while (cur_r < q.r) {
  86. 			cur_r++; 
  87. 			addRight(cur_r); 
  88. 		}
  89.  
  90. 		while (cur_l < q.l) {
  91. 			removeLeft(cur_l); 
  92. 			cur_l++; 
  93. 		}
  94.  
  95. 		while (cur_r > q.r) {
  96. 			removeRight(cur_r); 
  97. 			cur_r--; 
  98. 		}
  99.  
  100. 		ans[q.idx] = cur_ans; 
  101. 	}
  102.  
  103. 	for (int i = 0; i < q; i++) cout << ans[i] << '\n'; 
  104. }
Success #stdin #stdout 0s 5552KB
comments (?)
stdin
copy 
6 2 3
1 2 1 1 0 3
1 6
3 5
stdout
copy 
7
0
https://ideone.com/nymn1o
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!