Advertisement
Guest User

Untitled

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