fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. const int MOD = 1000000007;
  4. const int MAX = 200005;
  5. struct node
  6. {
  7. 	int a[32], t, x;
  8. 	node()
  9. 	{
  10. 		x = 0;
  11. 		t = 0;
  12. 	}
  13. } seg[4 * MAX], tmp;
  14. int a[MAX];
  15. node merge(node l, node r)
  16. {
  17. 	node ans;
  18. 	for (int _ = 0; _ < 2; _++)
  19. 	{
  20. 		for (int i = 0; i < l.t; i++)
  21. 		{
  22. 			int val = l.a[i];
  23. 			for (int j = 0; j < ans.t; j++)
  24. 				if (val & ans.a[j] & -ans.a[j])
  25. 					val ^= ans.a[j];
  26. 			if (val)
  27. 				ans.a[ans.t++] = val;
  28. 		}
  29. 		swap(l, r);
  30. 	}
  31. 	return ans;
  32. }
  33. void shift(int v)
  34. {
  35. 	seg[2 * v].x ^= seg[v].x;
  36. 	for (int i = 0; i < seg[2 * v].t; i++)
  37. 		if (seg[2 * v].a[i] & 1)
  38. 			seg[2 * v].a[i] ^= seg[v].x;
  39. 	seg[2 * v + 1].x ^= seg[v].x;
  40. 	for (int i = 0; i < seg[2 * v + 1].t; i++)
  41. 		if (seg[2 * v + 1].a[i] & 1)
  42. 			seg[2 * v + 1].a[i] ^= seg[v].x;
  43. 	seg[v].x = 0;
  44. }
  45. void build(int v, int s, int e)
  46. {
  47. 	if (e - s < 2)
  48. 	{
  49. 		seg[v].a[seg[v].t++] = a[s];
  50. 		return;
  51. 	}
  52. 	int mid = (s + e) / 2;
  53. 	build(2 * v, s, mid);
  54. 	build(2 * v + 1, mid, e);
  55. 	seg[v] = merge(seg[2 * v], seg[2 * v + 1]);
  56. }
  57. void upd(int l, int r, int val, int v, int s, int e)
  58. {
  59. 	if (l <= s && e <= r)
  60. 	{
  61. 		seg[v].x ^= val;
  62. 		for (int i = 0; i < seg[v].t; i++)
  63. 			if (seg[v].a[i] & 1)
  64. 				seg[v].a[i] ^= val;
  65. 		return;
  66. 	}
  67. 	if (e <= l || r <= s)
  68. 		return;
  69. 	shift(v);
  70. 	int mid = (s + e) / 2;
  71. 	upd(l, r, val, 2 * v, s, mid);
  72. 	upd(l, r, val, 2 * v + 1, mid, e);
  73. 	seg[v] = merge(seg[2 * v], seg[2 * v + 1]);
  74. }
  75. node get(int l, int r, int v, int s, int e)
  76. {
  77. 	if (l <= s && e <= r)
  78. 		return seg[v];
  79. 	if (e <= l || r <= s)
  80. 		return node();
  81. 	shift(v);
  82. 	int mid = (s + e) / 2;
  83. 	return merge(get(l, r, 2 * v, s, mid), get(l, r, 2 * v + 1, mid, e));
  84. }
  85. int main()
  86. {
  87. 	ios::sync_with_stdio(false);
  88. 	cin.tie(0);
  89. 	int n, q;
  90. 	cin >> n >> q;
  91. 	for (int i = 0; i < n; i++)
  92. 	{
  93. 		cin >> a[i];
  94. 		a[i] = a[i] * 2 + 1;
  95. 	}
  96. 	build(1, 0, n);
  97. 	while (q--)
  98. 	{
  99. 		int t;
  100. 		cin >> t;
  101. 		if (t == 2)
  102. 		{
  103. 			int l, r;
  104. 			cin >> l >> r;
  105. 			l--;
  106. 			node ans = get(l, r, 1, 0, n);
  107. 			for (int i = 0; i < ans.t; i++)
  108. 				if (ans.a[i] & 1)
  109. 					ans.a[i]--;
  110. 			cout << (1 << merge(ans, tmp).t) << "\n";
  111. 		}
  112. 		else
  113. 		{
  114. 			int l, r, val;
  115. 			cin >> l >> r >> val;
  116. 			l--;
  117. 			val *= 2;
  118. 			upd(l, r, val, 1, 0, n);
  119. 		}
  120. 	}
  121. 	return 0;
  122. }
  123.  
Time limit exceeded #stdin #stdout 5s 110464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WnPXQ4
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!