Advertisement
MegaVerkruzo

Untitled

Sep 23rd, 2019
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.01 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const long long INF = 1e9;
  6.  
  7. void build(vector<long long>& start, vector<long long>& z, int l, int r, int now) {
  8. if (l > r) {
  9. return;
  10. }
  11. if (l == r) {
  12. z[now] = start[l];
  13. return;
  14. }
  15. int mid = (l + r) / 2;
  16. build(start, z, l, mid, now * 2);
  17. build(start, z, mid + 1, r, now * 2 + 1);
  18. z[now] = min(z[now * 2], z[now * 2 + 1]);
  19. }
  20.  
  21. void push(vector<long long>& z, vector<long long>& ad, vector<long long>& f, int now) {
  22. if (f[now] != -1) {
  23. z[now] = f[now] + ad[now];
  24. f[now * 2] = f[now];
  25. f[now * 2 + 1] = f[now];
  26. f[now] = -1;
  27. ad[now] = 0;
  28. } else {
  29. z[now] += ad[now];
  30. ad[now * 2] += ad[now];
  31. ad[now * 2 + 1] += ad[now];
  32. ad[now] = 0;
  33. }
  34.  
  35. }
  36.  
  37. long long query(vector<long long>& z, vector<long long>& ad, vector<long long>& f, int l, int r, int a, int b, int now) {
  38. push(z, ad, f, now);
  39. if (r < a || l > b) {
  40. return INF;
  41. }
  42. if (a <= l && r <= b) {
  43. return z[now];
  44. }
  45. int mid = (l + r) / 2;
  46. return min(query(z, ad, f, l, mid, a, b, now * 2), query(z, ad, f, mid + 1, r, a, b, now * 2 + 1));
  47. }
  48.  
  49. void update_add(vector<long long>& z, vector<long long>& ad, vector<long long>& f, int l, int r, int delta, int a, int b, int now) {
  50. push(z, ad, f, now);
  51. if (r < a || l > b) {
  52. return;
  53. }
  54. if (a <= l && r <= b) {
  55. ad[now] += delta;
  56. push(z, ad, f, now);
  57. return;
  58. }
  59. int mid = (l + r) / 2;
  60. update_add(z, ad, f, l, mid, delta, a, b, now * 2);
  61. update_add(z, ad, f, mid + 1, r, delta, a, b, now * 2 + 1);
  62. z[now] = min(z[now * 2], z[now * 2 + 1]);
  63. }
  64.  
  65. void update_res(vector<long long>& z, vector<long long>& ad, vector<long long>& f, int l, int r, int value, int a, int b, int now) {
  66. push(z, ad, f, now);
  67. if (r < a || l > b) {
  68. return;
  69. }
  70. if (a <= l && r <= b) {
  71. f[now] = value;
  72. push(z, ad, f, now);
  73. return;
  74. }
  75. int mid = (l + r) / 2;
  76. update_res(z, ad, f, l, mid, value, a, b, now * 2);
  77. update_res(z, ad, f, mid + 1, r, value, a, b, now * 2 + 1);
  78. z[now] = min(z[now * 2], z[now * 2 + 1]);
  79. }
  80.  
  81. int main() {
  82. int n;
  83. cin >> n;
  84. vector<long long> start(n);
  85. for (int i = 0; i < n;++i) {
  86. cin >> start[i];
  87. }
  88. string s;
  89. vector<long long> ad(n * 6, 0);
  90. vector<long long> z(n * 6, INF);
  91. vector<long long> f(n * 6, -1);
  92. build(start, z, 0, n - 1, 1);
  93. while (cin >> s) {
  94. int l, r;
  95. cin >> l >> r;
  96. if (s == "min") {
  97. cout << query(z, ad, f, 0, n - 1, l - 1, r - 1, 1) << "\n";
  98. } else if (s == "set") {
  99. int val;
  100. cin >> val;
  101. update_res(z, ad, f, 0, n - 1, val, l - 1, r - 1, 1);
  102. } else {
  103. int val;
  104. cin >> val;
  105. update_add(z, ad, f, 0, n - 1, val, l - 1, r - 1, 1);
  106. }
  107. }
  108. return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement