fork download
copy 
  1. #include<bits\stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int mod = 1e9 + 7;
  5. //insted of define the data type of tree int 
  6. // i will define it as node 
  7. // and i can do any edit i wont in future
  8. // for any problem
  9. struct node
  10. {
  11. 	int sum = 0;
  12. 	int lazy = 1;
  13. 	int bo = 0;
  14. 	node(int x = 0) {
  15. 		sum = x;
  16. 		lazy = 1;
  17. 		bo = 0;
  18. 	}
  19.  
  20. };
  21. // when i go to range is not in query range 
  22. // what i well return
  23. //so i but it here to esay edit
  24. node out()
  25. {
  26. 	return node((int)0);
  27. }
  28. // when your answer will come from two child nodes 
  29. //How will you compute the value for this node
  30. node proces(node a, node b)
  31. {
  32. 	return node((a.sum + b.sum) % mod);
  33. }
  34. int const nn = 4e5 + 1;
  35. int n;
  36. int a[nn];
  37. node tree1[nn];
  38. // when will you build your tree i use one based
  39. // s=1  e=n  ind=1
  40. void build_tree(node *tree, int s, int e, int ind)
  41. {
  42. 	if (s == e)
  43. 	{
  44. 		tree[ind] = node(a[s]);
  45. 		return;
  46. 	}
  47. 	int mid = (s + e) / 2;
  48. 	build_tree(tree, s, mid, ind * 2);
  49. 	build_tree(tree, mid + 1, e, (ind * 2) + 1);
  50. 	tree[ind] = proces(tree[ind * 2], tree[(ind * 2) + 1]);
  51. 	return;
  52. }
  53. //ss segment start =1  se segment end =n l,r this is the range
  54. // v is the lazy value 
  55. //ind =1
  56. void updateRangeLazy(node *tree, int ss, int se, int l, int r, int v, int ind)
  57. {
  58. 	//before going down resolve the value if it exists
  59. 	// i the node i reach has lazy value i need to execute this value
  60. 	// and send the lazy value to the node's chidren 
  61. 	// and after that i go to see  what i will do with this node
  62.  
  63. 	if (tree[ind].bo != 0)
  64. 	{
  65. 		//This process will 
  66. 		//change from one problem to another
  67. 		tree[ind].sum *= tree[ind].lazy;
  68. 		tree[ind].sum %= mod;
  69. 		// non leaf node 
  70. 		// i will send the lazy value to my children
  71. 		if (ss != se)
  72. 		{
  73. 			// this type of update tree[ind * 2].lazy += tree[ind].lazy;
  74. 			// will change from porblem to another too
  75. 			tree[ind * 2].lazy *= tree[ind].lazy;
  76. 			tree[ind * 2 + 1].lazy *= tree[ind].lazy;
  77. 			tree[ind * 2 + 1].bo = 1;
  78. 			tree[ind * 2].lazy %= mod;
  79. 			tree[ind * 2 + 1].lazy %= mod;
  80. 			tree[ind * 2].bo = 1;
  81. 		}
  82. 		tree[ind].lazy = 1;
  83. 		tree[ind].bo = 0;
  84. 	}
  85.  
  86. 	// base  case
  87. 	// no overlap
  88. 	if (ss > r || l > se)
  89. 		return;
  90.  
  91. 	//another case- complete overlap case
  92. 	// i will change the value for this node 
  93. 	// and will send lazy value to my children if i am not
  94. 	// leaf node 
  95. 	if (ss >= l && se <= r)
  96. 	{
  97. 		// this process depend on this problem 
  98. 		tree[ind].sum *= v;
  99. 		tree[ind].sum %= mod;
  100.  
  101. 		// create a new lazy value of children node
  102. 		if (ss != se) {
  103. 			tree[ind * 2].lazy *= v;
  104. 			tree[ind * 2].lazy %= mod;
  105. 			tree[ind * 2 + 1].lazy *= v;
  106. 			tree[ind * 2 + 1].lazy %= mod;
  107. 			tree[ind * 2].bo = 1;
  108. 			tree[ind * 2 + 1].bo = 1;
  109. 		}
  110. 		return;
  111. 	}
  112. 	// if the case not complet overlap and not the first 
  113. 	// case this mean that is the third case when a part of
  114. 	// the update is included and another part is out of range
  115. 	// it is recursive case
  116.  
  117. 	int mid = (ss + se) / 2;
  118. 	updateRangeLazy(tree, ss, mid, l, r, v, ind * 2);
  119. 	updateRangeLazy(tree, mid + 1, se, l, r, v, ind * 2 + 1);
  120. 	//update tree[ind]
  121. 	tree[ind] = proces(tree[ind * 2], tree[ind * 2 + 1]);
  122. 	return;
  123. }
  124. //ss segment start =1  se=segment end =n 
  125. // qs,qe is my question
  126. //ind =1
  127. node queryLazy(node *tree, int ss, int se, int qs, int qe, int ind) {
  128. 	//before going down resolve the value if it exists
  129. 	// i the node i reach has lazy value i need to execute this value
  130. 	// and send the lazy value to the node's chidren 
  131. 	// and after that i go to see  what i will do with this node
  132.  
  133. 	if (tree[ind].bo != 0)
  134. 	{
  135. 		//This process will 
  136. 		//change from one problem to another
  137. 		tree[ind].sum *= tree[ind].lazy;
  138. 		tree[ind].sum %= mod;
  139. 		// non leaf node 
  140. 		// i will send the lazy value to my children
  141. 		if (ss != se)
  142. 		{
  143. 			// this type of update tree[ind * 2].lazy += tree[ind].lazy;
  144. 			// will change from porblem to another too
  145. 			tree[ind * 2].lazy *= tree[ind].lazy;
  146. 			tree[ind * 2 + 1].lazy *= tree[ind].lazy;
  147. 			tree[ind * 2].lazy %= mod;
  148. 			tree[ind * 2 + 1].lazy %= mod;
  149. 			tree[ind * 2 + 1].bo = 1;
  150. 			tree[ind * 2].bo = 1;
  151. 		}
  152. 		tree[ind].lazy = 1;
  153. 		tree[ind].bo = 0;
  154. 	}
  155. 	// query logic 
  156. 	//no overlap	
  157. 	if (ss > qe || se < qs)
  158. 		return out();
  159.  
  160. 	//complete overlap
  161. 	if (ss >= qs && se <= qe)
  162. 		return tree[ind];
  163. 	// another case-third case
  164. 	//recursive case
  165. 	int mid = (ss + se) / 2;
  166. 	node left = queryLazy(tree, ss, mid, qs, qe, ind * 2);
  167. 	node right = queryLazy(tree, mid + 1, se, qs, qe, ind * 2 + 1);
  168. 	return  proces(left, right);
  169.  
  170. }
  171. int32_t main()
  172. {
  173. 	int n, m;
  174. 	cin >> n >> m;
  175. 	for (int i = 1; i <= n; i++)
  176. 		a[i] = 1;
  177. 	build_tree(tree1, 1, n, 1);
  178. 	while (m--)
  179. 	{
  180. 		int ty;
  181. 		cin >> ty;
  182. 		if (ty == 1)
  183. 		{
  184. 			int l, r, v;
  185. 			cin >> l >> r >> v;
  186. 			l++;
  187. 			updateRangeLazy(tree1, 1, n, l, r, v, 1);
  188. 		}
  189. 		else {
  190. 			int l, r;
  191. 			cin >> l >> r;
  192. 			l++;
  193. 			cout << queryLazy(tree1, 1, n, l, r, 1).sum << endl;
  194. 		}
  195. 	}
  196.  
  197. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:1:9: fatal error: bits\stdc++.h: No such file or directory
 #include<bits\stdc++.h>
         ^~~~~~~~~~~~~~~
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/mIMB69
language:
C++14 (gcc 8.3)
created:
341 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!