Advertisement
Guest User

Untitled

a guest
Feb 24th, 2020
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.32 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define endl "\n"
  5. using namespace std;
  6. ll big_int_const = 1000000000000000001;
  7. ll min_int_const = -1000000000000000001;
  8. ll mod = 1000000000000000000;
  9. ll a[500000];
  10. ll a_set[500000];
  11. ll a_inc[500000];
  12. ll shift;
  13.  
  14. void propagate(ll position, ll left_now, ll right_now) {
  15.     if (a_set[position] != min_int_const) {
  16.         a[position] = a_set[position];
  17.         if (right_now != left_now) {
  18.             a_set[position * 2 + 1] = a_set[position];
  19.             a_set[position * 2 + 2] = a_set[position];
  20.             a_inc[position * 2 + 1] = 0;
  21.             a_inc[position * 2 + 2] = 0;
  22.         }
  23.         a_set[position] = min_int_const;
  24.  
  25.     }
  26.     if (a_inc[position] != 0) {
  27.         a[position] = (a[position] + a_inc[position]) % mod;
  28.         if (right_now != left_now) {
  29.             a_inc[position * 2 + 1] = (a_inc[position * 2 + 1] + a_inc[position]) % mod;
  30.             a_inc[position * 2 + 2] = (a_inc[position * 2 + 2] + a_inc[position]) % mod;
  31.         }
  32.         a_inc[position] = 0;
  33.     }
  34. }
  35.  
  36. void update(ll position, ll left_now, ll right_now, ll left, ll right, ll set_val, ll inc_val) {
  37.     propagate(position, left_now, right_now);
  38.     if (left > right_now || right < left_now)
  39.         return;
  40.     if (left_now >= left && right_now <= right) {
  41.         if (set_val != min_int_const) {
  42.             a_set[position] = set_val;
  43.         }
  44.         if (inc_val != 0) {
  45.             a_inc[position] = inc_val;
  46.         }
  47.         propagate(position, left_now, right_now);
  48.         return;
  49.     }
  50.     ll middle = (left_now + right_now) / 2;
  51.     update(position * 2 + 1, left_now, middle, left, right, set_val, inc_val);
  52.     update(position * 2 + 2, middle + 1, right_now, left, right, set_val, inc_val);
  53.     a[position] = min(a[position * 2 + 1], a[position * 2 + 2]);
  54. }
  55.  
  56.  
  57. ll get_min(ll position, ll left_now, ll right_now, ll left, ll right) {
  58.     propagate(position, left_now, right_now);
  59.     if (left > right_now || right < left_now)
  60.         return big_int_const;
  61.     if (left_now >= left && right_now <= right) {
  62.         return a[position];
  63.     }
  64.     ll middle = (left_now + right_now) / 2;
  65.     return min(get_min(2 * position + 1, left_now, middle, left, right),
  66.                get_min(2 * position + 2, middle + 1, right_now, left, right));
  67. }
  68.  
  69. void build(ll l, ll r) {
  70.     if (l != 0) {
  71.         for (ll i = l; i < r; i = i + 2) {
  72.             a[i / 2] = min(a[i], a[i + 1]);
  73.         }
  74.         build(l / 2, r / 2);
  75.     }
  76. }
  77.  
  78. int main() {
  79.     ll n;
  80.     cin >> n;
  81.     fill(begin(a), end(a), big_int_const);
  82.     fill(begin(a_set), end(a_set), min_int_const);
  83.     shift = (1 << (ll) ceil(log2(n))) - 1;
  84.     for (ll i = 0; i < n; i++) {
  85.         cin >> a[shift + i];
  86.     }
  87.     build(shift, 2 * shift);
  88. //    for (int i = 0; i < 2*shift; i++){
  89. //        cout << a[i] << " ";
  90. //    }
  91.     string s;
  92.     ll i, j;
  93.     while (cin >> s >> i >> j) {
  94.         i += shift;
  95.         j += shift;
  96.         if (s == "min") {
  97.             cout << get_min(0, shift, 2 * shift, i - 1, j - 1) << endl;
  98.         } else {
  99.             ll x;
  100.             cin >> x;
  101.             if (s == "set") {
  102.                 update(0, shift, 2 * shift, i - 1, j - 1, x, 0);
  103.             } else {
  104.                 update(0, shift, 2 * shift, i - 1, j - 1, min_int_const, x);
  105.             }
  106.         }
  107.     }
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement