fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define endl "\n"
  5.  
  6. struct segmentTree
  7. {
  8. #define L (2 * node + 1)
  9. #define R (2 * node + 2)
  10. #define mid ((left + right) >> 1)
  11. private:
  12. 	struct Node
  13. 	{
  14. 		ll value;
  15. 		Node() {}
  16. 		Node(const ll &N) : value(N) {}
  17. 	};
  18. 	int size;
  19. 	vector<Node> seg, lazyAssign, lazyAdd;
  20. 	Node merge(const Node &leftNode, const Node &rightNode)
  21. 	{
  22. 		Node res;
  23. 		res.value = (leftNode.value + rightNode.value);
  24. 		return res;
  25. 	}
  26. 	void build(int left, int right, int node, const vector<ll> &arr)
  27. 	{
  28. 		if (left == right)
  29. 		{
  30. 			if (left < arr.size())
  31. 				seg[node] = arr[left];
  32. 			return;
  33. 		}
  34. 		build(left, mid, L, arr);
  35. 		build(mid + 1, right, R, arr);
  36. 		seg[node] = merge(seg[L], seg[R]);
  37. 	}
  38. 	void push(int left, int right, int node)
  39. 	{
  40. 		if (lazyAssign[node].value != -1)
  41. 		{
  42. 			seg[node].value = (right - left + 1) * lazyAssign[node].value;
  43. 			if (left != right)
  44. 			{
  45. 				lazyAssign[L] = lazyAssign[node].value;
  46. 				lazyAdd[L] = 0;
  47.  
  48. 				lazyAssign[R] = lazyAssign[node].value;
  49. 				lazyAdd[R] = 0;
  50. 			}
  51. 			lazyAssign[node] = -1;
  52. 		}
  53. 		if (lazyAdd[node].value > 0)
  54. 		{
  55. 			seg[node].value += (right - left + 1) * lazyAdd[node].value;
  56. 			if (left != right)
  57. 			{
  58. 				lazyAdd[L].value += lazyAdd[node].value;
  59. 				lazyAdd[R].value += lazyAdd[node].value;
  60. 			}
  61. 			lazyAdd[node] = 0;
  62. 		}
  63. 	}
  64. 	void updateAdd(int left, int right, int node, int leftQuery, int rightQuery, const ll &val)
  65. 	{
  66. 		push(left, right, node);
  67. 		if (leftQuery > rightQuery)
  68. 			return;
  69.  
  70. 		if (left >= leftQuery && right <= rightQuery)
  71. 		{
  72. 			lazyAdd[node] = (lazyAdd[node].value + val);
  73. 			push(left, right, node);
  74. 			return;
  75. 		}
  76. 		updateAdd(left, mid, L, leftQuery, min(rightQuery, mid), val);
  77. 		updateAdd(mid + 1, right, R, max(leftQuery, mid + 1), rightQuery, val);
  78. 		seg[node] = merge(seg[L], seg[R]);
  79. 	}
  80. 	void updateAssign(int left, int right, int node, int leftQuery, int rightQuery, const ll &val)
  81. 	{
  82. 		push(left, right, node);
  83. 		if (leftQuery > rightQuery)
  84. 			return;
  85.  
  86. 		if (left >= leftQuery && right <= rightQuery)
  87. 		{
  88. 			lazyAssign[node] = val;
  89. 			lazyAdd[node] = 0;
  90. 			push(left, right, node);
  91. 			return;
  92. 		}
  93. 		updateAssign(left, mid, L, leftQuery, min(rightQuery, mid), val);
  94. 		updateAssign(mid + 1, right, R, max(leftQuery, mid + 1), rightQuery, val);
  95. 		seg[node] = merge(seg[L], seg[R]);
  96. 	}
  97. 	Node query(int left, int right, int node, int leftQuery, int rightQuery)
  98. 	{
  99. 		push(left, right, node);
  100. 		if (leftQuery > rightQuery || left > rightQuery || right < leftQuery)
  101. 			return 0;
  102.  
  103. 		if (left >= leftQuery && right <= rightQuery)
  104. 			return seg[node];
  105. 		Node leftSegment = query(left, mid, L, leftQuery, min(rightQuery, mid));
  106. 		Node rightSegment = query(mid + 1, right, R, max(leftQuery, mid + 1), rightQuery);
  107. 		return merge(leftSegment, rightSegment);
  108. 	}
  109.  
  110. public:
  111. 	segmentTree(const vector<ll> &arr)
  112. 	{
  113. 		size = 1;
  114. 		int n = arr.size();
  115. 		while (size < n)
  116. 			size <<= 1;
  117. 		seg = vector<Node>(2 * size, 0);
  118. 		lazyAssign = vector<Node>(2 * size, -1);
  119. 		lazyAdd = vector<Node>(2 * size, 0);
  120. 		build(0, size - 1, 0, arr);
  121. 	}
  122. 	void update(int left, int right, const ll &val, int type)
  123. 	{
  124. 		if (type == 1)
  125. 			updateAssign(0, size - 1, 0, left, right, val);
  126. 		else
  127. 			updateAdd(0, size - 1, 0, left, right, val);
  128. 	}
  129. 	ll query(int left, int right)
  130. 	{
  131. 		Node ans = query(0, size - 1, 0, left, right);
  132. 		return ans.value;
  133. 	}
  134.  
  135. #undef L
  136. #undef R
  137. #undef mid
  138. };
  139.  
  140. int main()
  141. {
  142. 	ios_base::sync_with_stdio(false);
  143. 	cin.tie(nullptr);
  144. #ifndef ONLINE_JUDGE
  145. 	freopen("input.txt", "r", stdin);
  146. 	freopen("Output.txt", "w", stdout);
  147. #endif //! ONLINE_JUDGE
  148. 	int t = 1;
  149. 	ll N, M;
  150. 	// cin >> t;
  151. 	while (t--)
  152. 	{
  153. 		cin >> N >> M;
  154. 		vector<ll> vc(N);
  155. 		for (int i{}; i < N; i++)
  156. 			cin >> vc[i];
  157. 		segmentTree segTree(vc);
  158.  
  159. 		while (M--)
  160. 		{
  161. 			ll query, L, R, val;
  162. 			cin >> query >> L >> R;
  163. 			L--, R--;
  164. 			if (query == 1 || query == 2)
  165. 			{
  166. 				cin >> val;
  167. 				segTree.update(L, R, val, query ^ 3);
  168. 			}
  169. 			else
  170. 				cout << segTree.query(L, R) << endl;
  171. 		}
  172. 	}
  173. 	return 0;
  174. }
Success #stdin #stdout #stderr 0.27s 40508KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected symbol in "using namespace"
Execution halted
https://ideone.com/0fRdaB
language:
R (R 3.5.2)
created:
4 days 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!