Advertisement
mk17ru

Untitled

Feb 24th, 2020
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.71 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define fi first
  4. #define si second
  5. using namespace std;
  6. const ll maxn = 200000;
  7. const ll inf = 1e18;
  8. ll n, m;
  9. ll a[maxn];
  10. ll t[maxn * 4];
  11. pair<ll, ll> nextt[4 * maxn];
  12. void prop(ll v) {
  13. if (nextt[v].si == 1) {
  14. nextt[v * 2] = nextt[v];
  15. nextt[v * 2 + 1] = nextt[v];
  16. } else {
  17. nextt[v * 2].fi += nextt[v].fi;
  18. nextt[v * 2 + 1].fi += nextt[v].fi;
  19. }
  20. if (nextt[v].si == 1) {
  21. t[v * 2] = nextt[v].fi;
  22. } else {
  23. t[v * 2] += nextt[v].fi;
  24. }
  25. if (nextt[v].si == 1) {
  26. t[v * 2 + 1] = nextt[v].fi;
  27. } else {
  28. t[v * 2 + 1] += nextt[v].fi;
  29. }
  30. nextt[v] = {0, 0};
  31.  
  32. return;
  33. }
  34. ll newFunction(ll a, ll b) {
  35. return min(a, b);
  36. }
  37.  
  38. void build(ll v, ll l, ll r) {
  39. if (l == r) {
  40. t[v] = a[l];
  41. return;
  42. }
  43. ll m = (r - l) / 2 + l;
  44. build(v * 2, l, m);
  45. build(v * 2 + 1, m + 1, r);
  46. t[v] = newFunction(t[v * 2], t[v * 2 + 1]);
  47. }
  48.  
  49. void update(ll v, ll l, ll r, ll L, ll R, ll val, ll type) {
  50. if (R < l || L > r) {
  51. return;
  52. }
  53. prop(v);
  54. if (l == L && r == R) {
  55. if (type == 1) {
  56. t[v] = val;
  57. nextt[v] = {val, 1};
  58. }
  59. else {
  60. t[v] += val;
  61. nextt[v] = {val, 0};
  62. }
  63. return;
  64. }
  65. ll m = (r - l) / 2 + l;
  66. update(v * 2, l, m, L, min(m, R), val, type);
  67. update(v * 2 + 1, m + 1, r, max(L, m + 1), R, val, type);
  68.  
  69. t[v] = newFunction(t[v * 2], t[v * 2 + 1]);
  70. }
  71.  
  72. ll mint(ll v, ll l, ll r, ll lx, ll rx) {
  73. if (lx > r || rx < l) {
  74. return inf;
  75. }
  76. prop(v);
  77. if (lx == l && rx == r) {
  78. return t[v];
  79. }
  80. ll m = (r - l) / 2 + l;
  81. ll a = mint(v * 2, l, m, lx, min(m, rx));
  82. ll b = mint(v * 2 + 1, m + 1, r, max(lx, m + 1), rx);
  83. return newFunction(a, b);
  84. }
  85.  
  86. int main() {
  87. ios::sync_with_stdio(0);
  88. cin.tie(0);
  89. cin >> n;
  90. for (ll i = 0; i < n; ++i) {
  91. cin >> a[i];
  92. }
  93. build(1, 0, n - 1);
  94. string s;
  95. while(cin >> s) {
  96. ll l, r, x;
  97. cin >> l >> r;
  98. if (s == "set") {
  99. cin >> x;
  100. update(1, 0, n - 1, l - 1, r - 1, x, 1);
  101. }
  102. if (s == "add") {
  103. cin >> x;
  104. update(1, 0, n - 1, l - 1, r - 1, x, 0);
  105. }
  106. if (s == "min") {
  107. cout << mint(1, 0, n - 1, l - 1, r - 1) <<"\n";
  108. }
  109. }
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement