Advertisement
Guest User

Untitled

a guest
Feb 17th, 2020
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define LL long long
  4.  
  5. using namespace std;
  6.  
  7. struct my_pair
  8. {
  9. LL v;
  10. int op;
  11. my_pair(int v1 = 0, LL op1 = 0)
  12. {
  13. v = v1;
  14. op = op1;
  15. }
  16. };
  17.  
  18. struct nodes
  19. {
  20. LL min_el;
  21. my_pair set_el;
  22. LL add;
  23. nodes(LL m = 0, my_pair s = my_pair(0, 0), LL a = 0)
  24. {
  25. min_el = m;
  26. set_el = my_pair(0, 0);
  27. add = a;
  28. }
  29. };
  30.  
  31. vector<nodes> SegmentTree;
  32. vector<LL> arr;
  33.  
  34. void out(string st, int v, int vl, int vr)
  35. {
  36. cout << st << " " << v << " " << vl << " " << vr << endl;
  37. for (int i = 0; i < SegmentTree.size(); i++)
  38. {
  39. cout << "v = " << i << " min = " << SegmentTree[i].min_el << " add = " << SegmentTree[i].add << " set = (" << SegmentTree[i].set_el.v << ", " << SegmentTree[i].set_el.op << ")" << endl;
  40. }
  41. return;
  42. }
  43.  
  44. void out()
  45. {
  46. cout << " !!!!!! " << endl;
  47. int pereh = 1;
  48. for (int i = 0; i < SegmentTree.size() - 1; i++)
  49. {
  50. if (pereh == i + 1)
  51. {
  52. cout << endl;
  53. pereh *= 2;
  54. }
  55. cout << "("<< SegmentTree[i].min_el << ", " << SegmentTree[i].add << ", (" << SegmentTree[i].set_el.v << ", " << SegmentTree[i].set_el.op << "))" << " ";
  56. }
  57. cout << endl;
  58. return;
  59. }
  60.  
  61. void build (int v, int vl, int vr)
  62. {
  63. if (vr - vl == 1)
  64. {
  65. SegmentTree[v].min_el = arr[vl];
  66. return;
  67. }
  68. int vm = (vl + vr) / 2;
  69. build(2 * v + 1, vl, vm);
  70. build(2 * v + 2, vm, vr);
  71. SegmentTree[v].min_el = min(SegmentTree[2 * v + 1].min_el, SegmentTree[2 * v + 2].min_el);
  72. }
  73.  
  74. void propogate(int v, int vl, int vr)
  75. {
  76. if (vr - vl == 1)
  77. {
  78. return;
  79. }
  80. if (SegmentTree[v].set_el.op == 0 && SegmentTree[v].add == 0)
  81. {
  82. return;
  83. }
  84. if (SegmentTree[v].set_el.op == 1)
  85. {
  86. SegmentTree[2 * v + 1].set_el = SegmentTree[v].set_el;
  87. SegmentTree[2 * v + 1].min_el = SegmentTree[v].set_el.v;
  88. SegmentTree[2 * v + 2].set_el = SegmentTree[v].set_el;
  89. SegmentTree[2 * v + 2].min_el = SegmentTree[v].set_el.v;
  90. SegmentTree[2 * v + 1].add = 0;
  91. SegmentTree[2 * v + 2].add = 0;
  92. SegmentTree[v].set_el = my_pair(0, 0);
  93. }
  94. SegmentTree[2 * v + 1].add += SegmentTree[v].add;
  95. SegmentTree[2 * v + 1].min_el += SegmentTree[v].add;
  96. SegmentTree[2 * v + 2].add += SegmentTree[v].add;
  97. SegmentTree[2 * v + 2].min_el += SegmentTree[v].add;
  98. SegmentTree[v].add = 0;
  99. }
  100.  
  101. LL min_el(int v, int vl, int vr, int l, int r)
  102. {
  103. // out("min", v, vl, vr);
  104. if (l <= vl && vr <= r)
  105. {
  106. return SegmentTree[v].min_el;
  107. }
  108. propogate(v, vl, vr);
  109. int vm = (vr + vl) / 2;
  110. if (r <= vm)
  111. {
  112. return min_el(2 * v + 1, vl, vm, l, r);
  113. }
  114. if (l >= vm)
  115. {
  116. return min_el(2 * v + 2, vm, vr, l, r);
  117. }
  118. return min(min_el(2 * v + 1, vl, vm, l, r), min_el(2 * v + 2, vm, vr, l, r));
  119. }
  120.  
  121.  
  122. void set_el(int v, int vl, int vr, int l, int r, LL x)
  123. {
  124. if (l >= vr || r <= vl)
  125. {
  126. return;
  127. }
  128. //out("set", v, vl, vr);
  129. if (l <= vl && vr <= r)
  130. {
  131. SegmentTree[v].min_el = x;
  132. SegmentTree[v].set_el = my_pair(x, 1);
  133. SegmentTree[v].add = 0;
  134. return;
  135. }
  136. propogate(v, vl, vr);
  137. int vm = (vr + vl) / 2;
  138. set_el(2 * v + 1, vl, vm, l, r, x);
  139. set_el(2 * v + 2, vm, vr, l, r, x);
  140. SegmentTree[v].min_el = min(SegmentTree[2 * v + 1].min_el, SegmentTree[2 * v + 2].min_el);
  141. }
  142.  
  143.  
  144. void add(int v, int vl, int vr, int l, int r, LL x)
  145. {
  146. if (r <= vl || l >= vr)
  147. {
  148. return;
  149. }
  150. //out("add", v, vl, vr);
  151. if (l <= vl && vr <= r)
  152. {
  153. SegmentTree[v].min_el = SegmentTree[v].min_el + x;
  154. SegmentTree[v].add += x;
  155. return;
  156. }
  157. propogate(v, vl, vr);
  158. int vm = (vr + vl) / 2;
  159. add(2 * v + 1, vl, vm, l, r, x);
  160. add(2 * v + 2, vm, vr, l, r, x);
  161. SegmentTree[v].min_el = min(SegmentTree[2 * v + 1].min_el, SegmentTree[2 * v + 2].min_el);
  162. }
  163.  
  164. int main()
  165. {
  166. int n;
  167. cin >> n;
  168. int bn = 1;
  169. while (bn < n)
  170. {
  171. bn *= 2;
  172. }
  173. arr.resize(bn);
  174. for (int i = 0; i < n; i++)
  175. {
  176. cin >> arr[i];
  177. }
  178. SegmentTree.resize(2 * bn);
  179. build(0, 0, bn);
  180. /*for (int i = 0; i < SegmentTree.size(); i++)
  181. cout << SegmentTree[i] << " ";
  182. cout << endl;*/
  183. string st;
  184. while (cin >> st)
  185. {
  186. if (st == "set")
  187. {
  188. int l, r;
  189. LL x;
  190. cin >> l >> r >> x;
  191. set_el(0, 0, bn, --l, r, x);
  192. //out();
  193. }
  194. if (st == "min")
  195. {
  196. int l, r;
  197. cin >> l >> r;
  198. cout << min_el(0, 0, bn, --l, r) << endl;
  199. //out();
  200. }
  201. if (st == "add")
  202. {
  203. int l, r;
  204. LL x;
  205. cin >> l >> r >> x;
  206. add(0, 0, bn, --l, r, x);
  207. //out();
  208. }
  209. }
  210. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement