fork(10) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std; 
  3. class ST {
  4. 	vector<int> seg, lazy; 
  5. public: 
  6. 	ST(int n) {
  7. 		seg.resize(4 * n); 
  8. 		lazy.resize(4 * n); 
  9. 	}
  10. public: 
  11. 	void build(int ind, int low, int high, int arr[]) {
  12. 		if(low == high) {
  13. 			seg[ind] = arr[low];
  14. 			return; 
  15. 		}
  16. 		int mid = (low + high) >> 1; 
  17. 		build(2*ind+1, low, mid, arr); 
  18. 		build(2*ind+2, mid+1, high, arr); 
  19. 		seg[ind] = seg[2*ind+1] + seg[2*ind+2];
  20. 	}
  21. public:
  22. 	void update(int ind, int low, int high, int l, int r, 
  23. 		int val) {
  24. 		// update the previous remaining updates 
  25. 		// and propogate downwards 
  26. 		if(lazy[ind] != 0) {
  27. 			seg[ind] += (high - low + 1) * lazy[ind]; 
  28. 			// propogate the lazy update downwards
  29. 			// for the remaining nodes to get updated 
  30. 			if(low != high) {
  31. 				lazy[2*ind+1] += lazy[ind]; 
  32. 				lazy[2*ind+2] += lazy[ind]; 
  33. 			}
  34.  
  35. 			lazy[ind] = 0; 
  36. 		}
  37.  
  38. 		// no overlap 
  39. 		// we don't do anything and return 
  40. 		// low high l r or l r low high 
  41. 		if(high < l or r < low) {
  42. 			return; 
  43. 		}
  44.  
  45. 		// complete overlap 
  46. 		// l low high r 
  47. 		if(low>=l && high <= r) {
  48. 			seg[ind] += (high - low + 1) * val; 
  49. 			// if a leaf node, it will have childrens
  50. 			if(low != high) {
  51. 				lazy[2*ind+1] += val; 
  52. 				lazy[2*ind+2] += val; 
  53. 			}
  54. 			return; 
  55. 		}
  56. 		// last case has to be no overlap case
  57. 		int mid = (low + high) >> 1; 
  58. 		update(2*ind+1, low, mid, l, r, val);
  59. 		update(2*ind+2, mid+1, high, l, r, val); 
  60. 		seg[ind] = seg[2*ind+1] + seg[2*ind+2]; 
  61. 	}
  62. public: 
  63. 	int query(int ind, int low, int high, int l, int r) {
  64.  
  65. 		// update if any updates are remaining 
  66. 		// as the node will stay fresh and updated 
  67. 		if(lazy[ind] != 0) {
  68. 			seg[ind] += (high - low + 1) * lazy[ind]; 
  69. 			// propogate the lazy update downwards
  70. 			// for the remaining nodes to get updated 
  71. 			if(low != high) {
  72. 				lazy[2*ind+1] += lazy[ind]; 
  73. 				lazy[2*ind+2] += lazy[ind]; 
  74. 			}
  75.  
  76. 			lazy[ind] = 0; 
  77. 		}
  78.  
  79. 		// no overlap return 0; 
  80. 		if(high < l or r < low) {
  81. 			return 0; 
  82. 		}
  83.  
  84. 		// complete overlap 
  85. 		if(low>=l && high <= r) return seg[ind]; 
  86.  
  87. 		int mid = (low + high) >> 1; 
  88. 		int left = query(2*ind+1, low, mid, l, r);
  89. 		int right = query(2*ind+2, mid+1, high, l, r);
  90. 		return left + right; 
  91. 	}
  92. };
  93.  
  94.  
  95. class STMin {
  96. 	vector<int> seg, lazy; 
  97. public: 
  98. 	STMin(int n) {
  99. 		seg.resize(4 * n); 
  100. 		lazy.resize(4 * n); 
  101. 	}
  102. public: 
  103. 	void build(int ind, int low, int high, int arr[]) {
  104. 		if(low == high) {
  105. 			seg[ind] = arr[low];
  106. 			return; 
  107. 		}
  108. 		int mid = (low + high) >> 1; 
  109. 		build(2*ind+1, low, mid, arr); 
  110. 		build(2*ind+2, mid+1, high, arr); 
  111. 		seg[ind] = min(seg[2*ind+1], seg[2*ind+2]);
  112. 	}
  113. public:
  114. 	void update(int ind, int low, int high, int l, int r, 
  115. 		int val) {
  116. 		// update the previous remaining updates 
  117. 		// and propogate downwards 
  118. 		if(lazy[ind] != 0) {
  119. 			seg[ind] += lazy[ind]; 
  120. 			// propogate the lazy update downwards
  121. 			// for the remaining nodes to get updated 
  122. 			if(low != high) {
  123. 				lazy[2*ind+1] += lazy[ind]; 
  124. 				lazy[2*ind+2] += lazy[ind]; 
  125. 			}
  126.  
  127. 			lazy[ind] = 0; 
  128. 		}
  129.  
  130. 		// no overlap 
  131. 		// we don't do anything and return 
  132. 		// low high l r or l r low high 
  133. 		if(high < l or r < low) {
  134. 			return; 
  135. 		}
  136.  
  137. 		// complete overlap 
  138. 		// l low high r 
  139. 		if(low>=l && high <= r) {
  140. 			seg[ind] += val; 
  141. 			// if a leaf node, it will have childrens
  142. 			if(low != high) {
  143. 				lazy[2*ind+1] += val; 
  144. 				lazy[2*ind+2] += val; 
  145. 			}
  146. 			return; 
  147. 		}
  148. 		// last case has to be no overlap case
  149. 		int mid = (low + high) >> 1; 
  150. 		update(2*ind+1, low, mid, l, r, val);
  151. 		update(2*ind+2, mid+1, high, l, r, val); 
  152. 		seg[ind] = min(seg[2*ind+1], seg[2*ind+2]); 
  153. 	}
  154. public: 
  155. 	int query(int ind, int low, int high, int l, int r) {
  156.  
  157. 		// update if any updates are remaining 
  158. 		// as the node will stay fresh and updated 
  159. 		if(lazy[ind] != 0) {
  160. 			seg[ind] += lazy[ind]; 
  161. 			// propogate the lazy update downwards
  162. 			// for the remaining nodes to get updated 
  163. 			if(low != high) {
  164. 				lazy[2*ind+1] += lazy[ind]; 
  165. 				lazy[2*ind+2] += lazy[ind]; 
  166. 			}
  167.  
  168. 			lazy[ind] = 0; 
  169. 		}
  170.  
  171. 		// no overlap return 0; 
  172. 		if(high < l or r < low) {
  173. 			return INT_MAX; 
  174. 		}
  175.  
  176. 		// complete overlap 
  177. 		if(low>=l && high <= r) return seg[ind]; 
  178.  
  179. 		int mid = (low + high) >> 1; 
  180. 		int left = query(2*ind+1, low, mid, l, r);
  181. 		int right = query(2*ind+2, mid+1, high, l, r);
  182. 		return min(left,right); 
  183. 	}
  184. };
  185.  
  186.  
  187. class ST {
  188. 	vector<int> seg, lazy; 
  189. public: 
  190. 	ST(int n) {
  191. 		seg.resize(4 * n); 
  192. 		lazy.resize(4 * n); 
  193. 	}
  194. public: 
  195. 	void build(int ind, int low, int high, int arr[]) {
  196. 		if(low == high) {
  197. 			seg[ind] = arr[low];
  198. 			return; 
  199. 		}
  200. 		int mid = (low + high) >> 1; 
  201. 		build(2*ind+1, low, mid, arr); 
  202. 		build(2*ind+2, mid+1, high, arr); 
  203. 		seg[ind] = seg[2*ind+1] + seg[2*ind+2];
  204. 	}
  205. public:
  206. 	void update(int ind, int low, int high, int l, int r, 
  207. 		int val) {
  208. 		// update the previous remaining updates 
  209. 		// and propogate downwards 
  210. 		if(lazy[ind] != 0) {
  211. 			seg[ind] = (high - low + 1) - seg[ind]; 
  212. 			// propogate the lazy update downwards
  213. 			// for the remaining nodes to get updated 
  214. 			if(low != high) {
  215. 				lazy[2*ind+1] = !lazy[2*ind + 1]; 
  216. 				lazy[2*ind+2] = !lazy[2*ind + 2]; 
  217. 			}
  218.  
  219. 			lazy[ind] = 0; 
  220. 		}
  221.  
  222. 		// no overlap 
  223. 		// we don't do anything and return 
  224. 		// low high l r or l r low high 
  225. 		if(high < l or r < low) {
  226. 			return; 
  227. 		}
  228.  
  229. 		// complete overlap 
  230. 		// l low high r 
  231. 		if(low>=l && high <= r) {
  232. 			seg[ind] = (high - low + 1) - val; 
  233. 			// if a leaf node, it will have childrens
  234. 			if(low != high) {
  235. 				lazy[2*ind+1] = !lazy[2*ind + 1]; 
  236. 				lazy[2*ind+2] = !lazy[2*ind + 2]; 
  237. 			}
  238. 			return; 
  239. 		}
  240. 		// last case has to be no overlap case
  241. 		int mid = (low + high) >> 1; 
  242. 		update(2*ind+1, low, mid, l, r, val);
  243. 		update(2*ind+2, mid+1, high, l, r, val); 
  244. 		seg[ind] = seg[2*ind+1] + seg[2*ind+2]; 
  245. 	}
  246. public: 
  247. 	int query(int ind, int low, int high, int l, int r) {
  248.  
  249. 		// update if any updates are remaining 
  250. 		// as the node will stay fresh and updated 
  251. 		if(lazy[ind] != 0) {
  252. 			seg[ind] = (high - low + 1) - seg[ind]; 
  253. 			// propogate the lazy update downwards
  254. 			// for the remaining nodes to get updated 
  255. 			if(low != high) {
  256. 				lazy[2*ind+1] = !lazy[2*ind + 1]; 
  257. 				lazy[2*ind+2] = !lazy[2*ind + 2]; 
  258. 			}
  259.  
  260. 			lazy[ind] = 0; 
  261. 		}
  262.  
  263. 		// no overlap return 0; 
  264. 		if(high < l or r < low) {
  265. 			return 0; 
  266. 		}
  267.  
  268. 		// complete overlap 
  269. 		if(low>=l && high <= r) return seg[ind]; 
  270.  
  271. 		int mid = (low + high) >> 1; 
  272. 		int left = query(2*ind+1, low, mid, l, r);
  273. 		int right = query(2*ind+2, mid+1, high, l, r);
  274. 		return left + right; 
  275. 	}
  276. };
  277. int main() {
  278. 	#ifndef ONLINE_JUDGE
  279. 	freopen("input.txt", "r", stdin); 
  280. 	freopen("output.txt", "w", stdout); 
  281. 	#endif
  282. 	int n;
  283. 	cin >> n; 
  284. 	int arr[n];
  285. 	for(int i = 0;i<n;i++) cin >> arr[i]; 
  286. 	ST st(n+1); 
  287. 	st.build(0,0,n-1, arr); 
  288.  
  289. 	int q;
  290. 	cin >> q; 
  291. 	while(q--) {
  292. 		int type;
  293. 		cin >> type; 
  294. 		if(type==1) {
  295. 			int l, r;
  296. 			cin >> l >> r;
  297. 			cout << st.query(0,0,n-1,l,r) << endl; 
  298. 		}
  299. 		else {
  300. 			int l, r, val;
  301. 			cin >> l >> r >> val; 
  302. 			st.update(0,0,n-1,l,r,val);
  303. 		}
  304. 	}
  305. 	return 0; 
  306. }
  307.  
  308.  
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: illegal character: '#'
#include<bits/stdc++.h>
^
Main.java:1: error: class, interface, or enum expected
#include<bits/stdc++.h>
        ^
Main.java:5: error: illegal start of type
public: 
      ^
Main.java:10: error: illegal start of type
public: 
      ^
Main.java:21: error: illegal start of type
public:
      ^
Main.java:41: error: ')' expected
		if(high < l or r < low) {
		           ^
Main.java:41: error: ';' expected
		if(high < l or r < low) {
		                ^
Main.java:41: error: variable declaration not allowed here
		if(high < l or r < low) {
		               ^
Main.java:41: error: > expected
		if(high < l or r < low) {
		                      ^
Main.java:62: error: illegal start of type
public: 
      ^
Main.java:80: error: ')' expected
		if(high < l or r < low) {
		           ^
Main.java:80: error: ';' expected
		if(high < l or r < low) {
		                ^
Main.java:80: error: variable declaration not allowed here
		if(high < l or r < low) {
		               ^
Main.java:80: error: > expected
		if(high < l or r < low) {
		                      ^
Main.java:97: error: illegal start of type
public: 
      ^
Main.java:102: error: illegal start of type
public: 
      ^
Main.java:113: error: illegal start of type
public:
      ^
Main.java:133: error: ')' expected
		if(high < l or r < low) {
		           ^
Main.java:133: error: ';' expected
		if(high < l or r < low) {
		                ^
Main.java:133: error: variable declaration not allowed here
		if(high < l or r < low) {
		               ^
Main.java:133: error: > expected
		if(high < l or r < low) {
		                      ^
Main.java:154: error: illegal start of type
public: 
      ^
Main.java:172: error: ')' expected
		if(high < l or r < low) {
		           ^
Main.java:172: error: ';' expected
		if(high < l or r < low) {
		                ^
Main.java:172: error: variable declaration not allowed here
		if(high < l or r < low) {
		               ^
Main.java:172: error: > expected
		if(high < l or r < low) {
		                      ^
Main.java:189: error: illegal start of type
public: 
      ^
Main.java:194: error: illegal start of type
public: 
      ^
Main.java:205: error: illegal start of type
public:
      ^
Main.java:225: error: ')' expected
		if(high < l or r < low) {
		           ^
Main.java:225: error: ';' expected
		if(high < l or r < low) {
		                ^
Main.java:225: error: variable declaration not allowed here
		if(high < l or r < low) {
		               ^
Main.java:225: error: > expected
		if(high < l or r < low) {
		                      ^
Main.java:246: error: illegal start of type
public: 
      ^
Main.java:264: error: ')' expected
		if(high < l or r < low) {
		           ^
Main.java:264: error: ';' expected
		if(high < l or r < low) {
		                ^
Main.java:264: error: variable declaration not allowed here
		if(high < l or r < low) {
		               ^
Main.java:264: error: > expected
		if(high < l or r < low) {
		                      ^
Main.java:277: error: class, interface, or enum expected
int main() {
^
Main.java:278: error: illegal character: '#'
	#ifndef ONLINE_JUDGE
	^
Main.java:280: error: class, interface, or enum expected
	freopen("output.txt", "w", stdout); 
	^
Main.java:281: error: illegal character: '#'
	#endif
	^
Main.java:282: error: class, interface, or enum expected
	int n;
	^
Main.java:283: error: class, interface, or enum expected
	cin >> n; 
	^
Main.java:284: error: class, interface, or enum expected
	int arr[n];
	^
Main.java:285: error: class, interface, or enum expected
	for(int i = 0;i<n;i++) cin >> arr[i]; 
	^
Main.java:285: error: class, interface, or enum expected
	for(int i = 0;i<n;i++) cin >> arr[i]; 
	              ^
Main.java:285: error: class, interface, or enum expected
	for(int i = 0;i<n;i++) cin >> arr[i]; 
	                  ^
Main.java:286: error: class, interface, or enum expected
	ST st(n+1); 
	^
Main.java:287: error: class, interface, or enum expected
	st.build(0,0,n-1, arr); 
	^
Main.java:289: error: class, interface, or enum expected
	int q;
	^
Main.java:290: error: class, interface, or enum expected
	cin >> q; 
	^
Main.java:291: error: class, interface, or enum expected
	while(q--) {
	^
Main.java:293: error: class, interface, or enum expected
		cin >> type; 
		^
Main.java:294: error: class, interface, or enum expected
		if(type==1) {
		^
Main.java:296: error: class, interface, or enum expected
			cin >> l >> r;
			^
Main.java:297: error: class, interface, or enum expected
			cout << st.query(0,0,n-1,l,r) << endl; 
			^
Main.java:298: error: class, interface, or enum expected
		}
		^
Main.java:301: error: class, interface, or enum expected
			cin >> l >> r >> val; 
			^
Main.java:302: error: class, interface, or enum expected
			st.update(0,0,n-1,l,r,val);
			^
Main.java:303: error: class, interface, or enum expected
		}
		^
Main.java:306: error: class, interface, or enum expected
}
^
62 errors
stdout
copy 
Standard output is empty
https://ideone.com/gvipU8
language:
Java (HotSpot 12)
created:
4 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!