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. const int MX = 6e6 + 5; 
  12.  
  13. struct Node {
  14. 	int nxt[2];   
  15. 	int cnt = 0;   
  16. 	ll sum = 0;  
  17. 	int mark = 0;
  18.  
  19. 	Node() {
  20. 		memset(nxt, -1, sizeof nxt); 
  21. 	}
  22. }; 
  23.  
  24. int sz;  
  25. Node trie[MX]; 
  26.  
  27. void addNumber(int x) {
  28. 	int v = 0;   
  29. 	for (int i = 29; i >= 0; i--) {
  30. 		int c = (x >> i) & 1;  
  31. 		if (trie[v].nxt[c] == -1) {
  32. 			trie[v].nxt[c] = ++sz;  
  33. 		}
  34. 		v = trie[v].nxt[c]; 
  35. 		trie[v].cnt++; 
  36. 		trie[v].sum += x;  
  37. 	}
  38. 	trie[v].mark++; 
  39. }
  40.  
  41. // Kiểm tra số nguyên x có tồn tại trong cây trie hiện tại hay không
  42. bool exist(int x) {
  43. 	int v = 0;   
  44. 	for (int i = 29; i >= 0; i--) {
  45. 		int c = (x >> i) & 1; 
  46. 		int nxt_v = trie[v].nxt[c]; 
  47. 		if (nxt_v == -1 || trie[nxt_v].cnt == 0) return false; 
  48. 		v = nxt_v;  
  49. 	}
  50. 	return (trie[v].mark > 0); 
  51. }
  52.  
  53. void removeNumber(int x) {
  54. 	if (!exist(x)) return; 
  55. 	int v = 0;  
  56. 	for (int i = 29; i >= 0; i--) {
  57. 		int c = (x >> i) & 1;   
  58. 		v = trie[v].nxt[c]; 
  59. 		trie[v].cnt--; 
  60. 		trie[v].sum -= x; 
  61. 	}
  62. 	trie[v].mark--; 
  63. }
  64.  
  65. // Tính tổng các số nguyên x <= mx có trong cây trie
  66. ll getSum(int mx) {
  67. 	if (mx < 0) return 0;    
  68.  
  69. 	int v = 0; ll ans = 0;   
  70. 	for (int i = 29; i >= 0; i--) {
  71. 		int c_mx = (mx >> i) & 1; 
  72. 		int nxt_v0 = trie[v].nxt[0], nxt_v1 = trie[v].nxt[1]; 
  73.  
  74. 		if (c_mx == 0) {
  75. 			v = nxt_v0;  
  76. 		}
  77. 		else {
  78. 			if (nxt_v0 != -1) ans += trie[nxt_v0].sum; 
  79. 			v = nxt_v1; 	
  80. 		}
  81.  
  82. 		if (v == -1) break; 
  83. 	}
  84. 	if (v != -1) ans += trie[v].sum;    
  85.  
  86. 	return ans; 
  87. }
  88.  
  89. // Tìm số nhỏ thứ k 
  90. int findKth(int k) {
  91. 	int v = 0, ans = 0;  
  92. 	for (int i = 29; i >= 0; i--) {
  93. 		for (int c = 0; c <= 1; c++) {
  94. 			int nxt_v = trie[v].nxt[c]; 
  95. 			if (nxt_v == -1) continue; 
  96. 			if (k <= trie[nxt_v].cnt) {
  97. 				v = nxt_v;   
  98. 				ans |= c * (1 << i);
  99. 				break;  	
  100. 			}
  101. 			else {
  102. 				k -= trie[nxt_v].cnt; 
  103. 			}
  104. 		}
  105. 	}
  106. 	return ans; 
  107. }
  108.  
  109. // Tìm số nguyên x có trong cây trie sao cho (x ^ a) lớn nhất
  110. int findMaxXor(int a) {
  111. 	int v = 0, ans = 0;  
  112. 	// Tại mỗi bước, ưu tiên đi vào nhánh cho ra xor bằng 1 
  113. 	for (int i = 29; i >= 0; i--) {
  114. 		int c_a = (a >> i) & 1;   
  115. 		int nxt_v0 = trie[v].nxt[c_a], nxt_v1 = trie[v].nxt[c_a ^ 1];
  116.  
  117. 		if (nxt_v1 != -1 && trie[nxt_v1].cnt > 0) {
  118. 			v = nxt_v1;  
  119. 			ans |= (1 << i); 
  120. 		}
  121. 		else {
  122. 			v = nxt_v0; 	
  123. 		}
  124. 	}
  125. 	return ans; 
  126. }
  127.  
  128. int q;  
  129.  
  130. int main() {
  131. 	ios::sync_with_stdio(false); 
  132. 	cin.tie(nullptr); 	
  133. 	cin >> q; 
  134.  
  135. 	while (q--) {
  136. 		int type; cin >> type; 
  137.  
  138. 		if (type == 1) {
  139. 			int x; cin >> x; 
  140. 			addNumber(x); 
  141. 		}
  142.  
  143. 		if (type == 2) {
  144. 			int x; cin >> x; 
  145. 			removeNumber(x); 
  146. 		}
  147.  
  148. 		if (type == 3) {
  149. 			int l, r;  
  150. 			cin >> l >> r; 
  151. 			ll ans = getSum(r) - getSum(l - 1); 
  152. 			cout << ans << '\n'; 
  153. 		}
  154.  
  155. 		if (type == 4) {
  156. 			int k; cin >> k;
  157. 			int ans = findKth(k);  
  158. 			cout << ans << '\n'; 
  159. 		}
  160.  
  161. 		if (type == 5) {
  162. 			int a; cin >> a; 
  163. 			int ans = findMaxXor(a);  
  164. 			cout << ans << '\n'; 
  165. 		}
  166. 	}
  167. }
Success #stdin #stdout 0.03s 190996KB
comments (?)
stdin 
10
1 3
1 4
3 1 3
4 2
1 2
2 2
4 1
2 5
3 1 6
5 8
stdout 
3
4
3
7
12
https://ideone.com/3kMa25
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!