fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty