http://codeforces.com/contest/665/problem/E

给出 n 个整数 a[1], a[2], ..., a[n]。 问有多少区间的亦或和大于等于 k。

Input

n k
a[1] a[2] ... a[n]

1 ≤ n ≤ 1e6
1 ≤ k ≤ 1e9
0 ≤ a[i] ≤ 1e9

Output

亦或和大于等于 k 的区间个数。

Examples

Case 1

3 1
1 2 3

5

Case 2

3 2
1 2 3

3

Case 3

3 3
1 2 3

2

Solution

处理前缀亦或和 s[i]。转化选择两个数 s[i] 和 s[j] （0 <= i < j <= n），使得 s[i] ^ s[j] >= k。这是个经典问题，使用将每个数看做是 31 位比特串（最高位看做第一个字符）。 对于每个 i，所有 s[j]（0 <= j < i）插入到字典树中。字典树每个节点还要记录经过该点的字符串的数目。

如此一来我们考查 s[j] 和 k，如果第 i 位有 2ⁱ >= k，那么，如果选择与 s[j] 的第 i 位不相同的位，那么亦或的结果中就有 2ⁱ，也就是说一定满足要求，故上述方向上字典树里的单词数目应该全部加到答案上，字典树上只需走相反的方法再计算；反之，如果 2ⁱ < k，如果选择与 s[j] 的 第 i 相同的位，当前位的亦或为 0，后面即使全部都是 1 也不会比 2ⁱ 大，故肯定是不能让总亦或值大于等于 k，所以一定要走另外的方向，并且使得 k -= 2ⁱ。

综上，字典树的每一层只走一个点。当然，计数完 s[j] 之后要将 s[j] 插入字典树，以便判断下一个数。总之，可以在 O(nlog(n)) 的时间内通过本题。

Code

1. #include <stdio.h> 
2. #include <string.h> 
3.  
4. #include <vector> 
5.  
6. const int N = 1000000 + 100; 
7.  
8. int a[N]; 
9.  
10. struct trie_t 
11. { 
12. #define each_bit(i) for (int i = 30; i >= 0; --i) 
13.  
14. struct node 
15. { 
16. int nxt[2]; 
17. int cnt; 
18.  
19. node() 
20. { 
21. cnt = 0; 
22. nxt[0] = nxt[1] = -1; 
23. } 
24. }; 
25.  
26. std::vector<node> v; 
27.  
28. void init() 
29. { 
30. // v.clear(); 
31. v.push_back(node()); 
32. } 
33.  
34. void insert(int x) 
35. { 
36. int now = 0; 
37. v[0].cnt++; 
38. each_bit(i) { 
39. int b = ((x >> i) & 1); 
40. if (v[now].nxt[b] == -1) { 
41. v[now].nxt[b] = v.size(); 
42. v.push_back(node()); 
43. } 
44. now = v[now].nxt[b]; 
45. v[now].cnt++; 
46. } 
47. } 
48.  
49. int count(int x, int k) 
50. { 
51. int now = 0; 
52. int ans = 0; 
53. each_bit(i) { 
54. int b = ((x >> i) & 1); 
55. if ((1 << i) >= k) { 
56. // numbers via nxt[!b] are big enough 
57. if (v[now].nxt[!b] != -1) { 
58. ans += v[v[now].nxt[!b]].cnt; 
59. } 
60. now = v[now].nxt[b]; 
61. } 
62. else { // (1 << i) < k 
63. // numbers via nxt[b] are too small 
64. now = v[now].nxt[!b]; 
65. k -= (1 << i); 
66. } 
67. if (now == -1) { 
68. break; 
69. } 
70. } 
71. return ans; 
72. } 
73. #undef each_bit 
74. } trie; 
75.  
76. int main() 
77. { 
78. int n, k; 
79. scanf("%d %d", &n, &k); 
80. for (int i = 1; i <= n; ++i) { 
81. scanf("%d", a+i); 
82. a[i] ^= a[i-1]; 
83. } 
84.  
85. long long ans = 0; 
86. trie.init(); 
87. for (int i = 0; i <= n; ++i) { 
88. ans += trie.count(a[i], k); 
89. trie.insert(a[i]); 
90. } 
91. printf("%I64d\n", ans); 
92. return 0; 
93. } 

转载于:https://www.cnblogs.com/gu-castle/p/5518237.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/95304750

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。