fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6. #define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
  7. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  8. #define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
  9. #define rep(i, c) for(auto &(i) : (c))
  10. #define x first
  11. #define y second
  12. #define pb push_back
  13. #define PB pop_back()
  14. #define iOS ios_base::sync_with_stdio(false)
  15. #define sqr(a) (((a) * (a)))
  16. #define all(a) a.begin() , a.end()
  17. #define error(x) cerr << #x << " = " << (x) <<endl
  18. #define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
  19. #define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
  20. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  21. #define L(x) ((x)<<1)
  22. #define R(x) (((x)<<1)+1)
  23. #define umap unordered_map
  24. #define double long double
  25. typedef long long ll;
  26. typedef pair<int,int>pii;
  27. typedef vector<int> vi;
  28. typedef complex<double> point;
  29. template <typename T> using os =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  30. template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
  31. template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}
  32. const int maxn = 2e5 + 10;
  33. inline int sbit(const int &x){return x & -x;}
  34. struct basis{
  35. 	int t = 0, a[32] = {};
  36. 	inline void pb(int x){
  37. 		For(i,0,t)
  38. 			if(x & sbit(a[i]))
  39. 				x ^= a[i];
  40. 		if(!x)	return ;
  41. 		For(i,0,t)
  42. 			if(sbit(x) & a[i])
  43. 				a[i] ^= x;
  44. 		a[t ++] = x;
  45. 	}
  46. 	inline void perform(int k){
  47. 		For(i,0,t)
  48. 			if(a[i] & 1)
  49. 				a[i] ^= k;
  50. 	}
  51. 	inline basis operator + (basis b){
  52. 		if(!t)	return b;
  53. 		if(!b.t)	return *this;
  54. 		basis ans;
  55. 		For(i,0,t)
  56. 			ans.pb(a[i]);
  57. 		For(i,0,b.t)
  58. 			ans.pb(b.a[i]);
  59. 		return ans;
  60. 	}
  61. }v[maxn * 4], emp;
  62. int lz[maxn * 4], a[maxn], n, q, p2[35];
  63. inline void upd(int id, int k){
  64. 	if(!k)	return ;
  65. 	lz[id] ^= k;
  66. 	v[id].perform(k);
  67. }
  68. inline void shift(int id){
  69. 	upd(L(id), lz[id]);
  70. 	upd(R(id), lz[id]);
  71. 	lz[id] = 0;
  72. }
  73. inline void build(int id = 1, int l = 0, int r = n){
  74. 	if(r - l < 2){
  75. 		v[id].pb(a[l]);
  76. 		return ;
  77. 	}
  78. 	int mid = (l + r)/2;
  79. 	build(L(id), l, mid);
  80. 	build(R(id), mid, r);
  81. 	v[id] = v[L(id)] + v[R(id)];
  82. }
  83. inline void upd(int x, int y, int k, int id = 1, int l = 0, int r = n){
  84. 	if(x >= r or l >= y)	return ;
  85. 	if(x <= l && r <= y){
  86. 		upd(id, k);
  87. 		return ;
  88. 	}
  89. 	int mid = (l + r)/2;
  90. 	shift(id);
  91. 	upd(x, y, k, L(id), l, mid);
  92. 	upd(x, y, k, R(id), mid, r);
  93. 	v[id] = v[L(id)] + v[R(id)];
  94. }
  95. inline basis ask(int x, int y, int id = 1, int l = 0, int r = n){
  96. 	if(x >= r or l >= y)	return emp;
  97. 	if(x <= l && r <= y)	return v[id];
  98. 	int mid = (l + r)/2;
  99. 	shift(id);
  100. 	return ask(x, y, L(id), l, mid) + ask(x, y, R(id), mid, r);
  101. }
  102. int main(){
  103. 	scanf("%d %d", &n, &q);
  104. 	For(i,0,n){
  105. 		scanf("%d", a + i);
  106. 		a[i] = 2*a[i] + 1;
  107. 	}
  108. 	build();
  109. 	For(i,0,35)	p2[i] = (1 << i);
  110. 	while(q --){
  111. 		int t, l, r, k;
  112. 		scanf("%d %d %d", &t, &l, &r);
  113. 		-- l;
  114. 		if(t == 1){
  115. 			scanf("%d", &k);
  116. 			upd(l, r, k << 1);
  117. 		}
  118. 		else{
  119. 			basis ans, b = ask(l, r);
  120. 			For(i,0,b.t)
  121. 				ans.pb(b.a[i] >> 1);
  122. 			printf("%d\n", p2[ans.t]);
  123. 		}
  124. 	}
  125. 	return 0;
  126. }
  127.  
Success #stdin #stdout 0s 110528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GnOXuG
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!