fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ull unsigned long long
  4. struct node
  5. {
  6. 	unsigned long long data;
  7. 	bool lazy , query1 , query2;
  8. 	node *left , *right;
  9. };
  10. node *build(ull a[] , int strt , int end)
  11. {
  12. 	node *temp = (node *)malloc(sizeof(node));
  13. 	if(strt == end)
  14. 	{
  15. 		temp->data = a[strt];
  16. 		temp->left = temp->right = NULL;
  17. 		temp->lazy = 0;
  18. 		temp->query1 = temp->query2 = 0;
  19. 		return temp;
  20. 	}
  21. 	int mid = (strt + end)/2;
  22.  
  23. 	temp->left = build(a , strt,  mid);
  24. 	temp->right = build(a , mid + 1 , end);
  25. 	temp->data = temp->left->data ^ temp->right->data;
  26. 	temp->lazy = 0;
  27. 	temp->query1 = temp->query2 = 0;
  28. 	return temp;
  29. }
  30. void rangeupdate(node *root , int strt , int end , int x , int y , bool flag)
  31. {
  32. 	if(strt >= x && end <= y)
  33. 	{
  34. 		if(!root->lazy)
  35. 		{
  36. 			if(!((end - strt + 1) & 1))
  37. 			{
  38. 				if(((end - strt + 1)/2) & 1)
  39. 					root->data = ~root->data;
  40. 			}
  41. 			else
  42. 			{
  43. 				if((flag && (((end - strt + 1)/2) & 1))||(!flag && !(((end - strt + 1)/2) & 1)))
  44. 					root->data = ~root->data;
  45.  
  46. 			}
  47. 			if(!flag)
  48. 			{
  49. 				root->query1 = 1;
  50. 				root->query2 = 0;
  51. 			}
  52. 			else
  53. 			{
  54. 				root->query1 = 0;
  55. 				root->query2 = 1;
  56. 			}
  57. 			root->lazy = 1;
  58. 		}
  59. 		else
  60. 		{
  61. 			if(flag)
  62. 			{
  63. 				root->query2 = !root->query2;
  64. 				if(!root->query1 && !root->query2)
  65. 					root->lazy = 0;
  66. 				if(!((end - strt + 1) & 1))
  67. 				{
  68. 					if(((end - strt + 1)/2) & 1)
  69. 						root->data = ~root->data;
  70. 				}
  71. 				else
  72. 				{
  73. 					if((((end - strt + 1)/2) & 1))
  74. 						root->data = ~root->data;
  75. 				}
  76. 			}
  77. 			else
  78. 			{
  79. 				root->query1 = !root->query1;
  80. 				if(!root->query1 && !root->query2)
  81. 					root->lazy = 0;
  82. 				if(!((end - strt + 1) & 1))
  83. 				{
  84. 					if(((end - strt + 1)/2) & 1)
  85. 						root->data = ~root->data;
  86. 				}
  87. 				else
  88. 				{
  89. 					if(!(((end - strt + 1)/2) & 1))
  90. 						root->data = ~root->data;
  91. 				}
  92. 			}
  93. 		}
  94. 		return;
  95. 	}
  96.  
  97. 	int mid = (strt + end)/2;
  98.  
  99. 	if(root->lazy)
  100. 	{
  101. 		if(root->query1)
  102. 			rangeupdate(root->left , strt , mid , strt , mid , 0);
  103. 		if(root->query2)
  104. 			rangeupdate(root->left , strt , mid , strt,  mid , 1);
  105. 		if(!((mid - strt + 1) & 1))
  106. 		{
  107. 			if(root->query1)
  108. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 0);
  109. 			if(root->query2)
  110. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 1);
  111. 		}
  112. 		else
  113. 		{
  114. 			if(root->query1)
  115. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 1);
  116. 			if(root->query2)
  117. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 0);
  118. 		}
  119. 		root->lazy = root->query1 = root->query2 = 0;
  120. 	}
  121.  
  122. 	if(y <= mid)
  123. 		rangeupdate(root->left , strt , mid , x , y , flag);
  124. 	else if(x > mid)
  125. 		rangeupdate(root->right , mid + 1 , end , x , y , flag);
  126. 	else
  127. 	{
  128. 		rangeupdate(root->left , strt , mid , x , mid , flag);
  129. 		if(!((mid - x + 1) & 1))
  130. 		{
  131. 			if(flag == 0)
  132. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , y , 0);
  133. 			else
  134. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , y , 1);
  135. 		}
  136. 		else
  137. 		{
  138. 			if(flag == 0)
  139. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , y , 1);
  140. 			else
  141. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , y , 0);
  142. 		}
  143. 	}
  144. 	root->data = root->left->data ^ root->right->data;
  145. }
  146. void pointupdate(node *root , int strt , int end , int x , ull y)
  147. {
  148. 	if(strt == end)
  149. 	{
  150. 		root->data = y;
  151. 		return;
  152. 	}
  153. 	int mid = (strt + end)/2;
  154.  
  155. 	if(root->lazy)
  156. 	{
  157. 		if(root->query1)
  158. 			rangeupdate(root->left , strt , mid , strt , mid , 0);
  159. 		if(root->query2)
  160. 			rangeupdate(root->left , strt , mid , strt,  mid , 1);
  161. 		if(!((mid - strt + 1) & 1))
  162. 		{
  163. 			if(root->query1)
  164. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 0);
  165. 			if(root->query2)
  166. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 1);
  167. 		}
  168. 		else
  169. 		{
  170. 			if(root->query1)
  171. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 1);
  172. 			if(root->query2)
  173. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 0);
  174. 		}
  175. 		root->lazy = root->query1 = root->query2 = 0;
  176. 	}
  177.  
  178. 	if(x <= mid)
  179. 		pointupdate(root->left , strt,  mid , x , y);
  180. 	else
  181. 		pointupdate(root->right , mid + 1 , end , x , y);
  182.  
  183. 	root->data = root->left->data ^ root->right->data;
  184. }
  185. ull pointquery(node *root , int strt , int end , int x)
  186. {
  187. 	if(strt == end)
  188. 		return root->data;
  189.  
  190. 	int mid = (strt + end)/2;
  191. 	if(root->lazy)
  192. 	{
  193. 		if(root->query1)
  194. 			rangeupdate(root->left , strt , mid , strt , mid , 0);
  195. 		if(root->query2)
  196. 			rangeupdate(root->left , strt , mid , strt,  mid , 1);
  197. 		if(!((mid - strt + 1) & 1))
  198. 		{
  199. 			if(root->query1)
  200. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 0);
  201. 			if(root->query2)
  202. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 1);
  203. 		}
  204. 		else
  205. 		{
  206. 			if(root->query1)
  207. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 1);
  208. 			if(root->query2)
  209. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 0);
  210. 		}
  211. 		root->lazy = root->query1 = root->query2 = 0;
  212. 	}
  213.  
  214. 	if(x <= mid)
  215. 		return pointquery(root->left , strt , mid , x);
  216. 	else
  217. 		return pointquery(root->right , mid + 1 , end , x);
  218. }
  219. ull rangequery(node *root , int strt , int end , int x , int y)
  220. {
  221. 	if(strt >= x && end <= y)
  222. 		return root->data;
  223.  
  224. 	int mid = (strt + end)/2;
  225. 	if(root->lazy)
  226. 	{
  227. 		if(root->query1)
  228. 			rangeupdate(root->left , strt , mid , strt , mid , 0);
  229. 		if(root->query2)
  230. 			rangeupdate(root->left , strt , mid , strt,  mid , 1);
  231. 		if(!((mid - strt + 1) & 1))
  232. 		{
  233. 			if(root->query1)
  234. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 0);
  235. 			if(root->query2)
  236. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 1);
  237. 		}
  238. 		else
  239. 		{
  240. 			if(root->query1)
  241. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 1);
  242. 			if(root->query2)
  243. 				rangeupdate(root->right , mid + 1 , end , mid + 1 , end , 0);
  244. 		}
  245. 		root->lazy = root->query1 = root->query2 = 0;
  246. 	}
  247.  
  248. 	if(y <= mid)
  249. 		return rangequery(root->left , strt , mid , x , y);
  250. 	else if(x > mid)
  251. 		return rangequery(root->right , mid + 1 , end , x , y);
  252. 	else
  253. 		return rangequery(root->left , strt , mid , x , mid)^rangequery(root->right , mid + 1 , end , mid + 1 , y);
  254. }
  255. int main()
  256. {
  257. 	int n ,i;
  258. 	cin >> n;
  259. 	ull a[n];
  260. 	for(i = 0;i < n;i++)
  261. 		cin >> a[i];
  262.  
  263. 	node *root = NULL;
  264. 	root = build(a , 0 , n-1);
  265. 	ull x , y , q;
  266. 	cin >> q;
  267. 	char t;
  268. 	while(q--)
  269. 	{
  270. 		cin >> t;
  271. 		if(t == 'A')
  272. 		{
  273. 			cin >> x >> y;
  274. 			pointupdate(root , 0 , n-1 , x-1 , y);
  275. 		}
  276. 		else if(t == 'B')
  277. 		{
  278. 			cin >> x >> y;
  279. 			rangeupdate(root , 0 , n-1 , x-1 , y-1 , 0);
  280. 		}
  281. 		else if(t == 'C')
  282. 		{
  283. 			cin >> x;
  284. 			cout << pointquery(root , 0 , n-1 , x-1) << endl;
  285. 		}
  286. 		else
  287. 		{
  288. 			cin >> x >> y;
  289. 			cout << rangequery(root , 0 , n-1 , x-1 , y-1) << endl;
  290. 		}
  291. 	}
  292. 	return 0;
  293. }
  294.  
Success #stdin #stdout 0s 3280KB
comments (?)
stdin
copy 
5
1 2 3 4 5
5
A 1 2
C 1
B 3 4
D 1 5
D 3 5
stdout
copy 
2
18446744073709551613
18446744073709551613
https://ideone.com/0RPkJD
language:
C++ (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!