ivnikkk

Untitled

Jan 24th, 2022
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.03 KB | None | 0 0
  1. #pragma GCC optimize("03")
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. using namespace chrono;
  6. #define all(a) a.begin(), a.end()
  7. #define allr(a) a.rbegin(), a.rend()
  8. #define endl "\n"
  9. mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  10. typedef long long ll;
  11. typedef long double ld;
  12. struct Segtree {
  13.     const ll inf = 1e18;
  14.     vector<ll>tree;
  15.     vector<ll>mod;
  16.     void build(ll v, ll tl, ll tr, vector<ll>& a) {
  17.         if (tl == tr) {
  18.             tree[v] = a[tl];
  19.             return;
  20.         }
  21.         ll mid = (tl + tr) / 2;
  22.         build(v * 2, tl, mid, a);
  23.         build(v * 2 + 1, mid + 1, tr, a);
  24.         tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
  25.     }
  26.     void init(ll n, vector<ll>& a) {
  27.         tree.resize(4 * n, -inf);
  28.         mod.resize(4 * n, 0);
  29.         build(1, 0, n - 1, a);
  30.     }
  31.     void push(ll v) {
  32.         tree[v] += mod[v];
  33.         if (v * 2 + 1 > (ll)tree.size()) {
  34.             mod[v] = 0;
  35.             return;
  36.         }
  37.         mod[v * 2] += mod[v];
  38.         mod[v * 2 + 1] += mod[v];
  39.         mod[v] = 0;
  40.     }
  41.     ll get(ll v, ll tl, ll tr, ll l, ll r) {
  42.         push(v);
  43.         if (tl > r || tr < l) {
  44.             return -inf;
  45.         }
  46.         if (tl >= l && tr <= r) {
  47.             return tree[v];
  48.         }
  49.         ll mid = (tl + tr) / 2;
  50.         return max(get(v * 2, tl, mid, l, r), get(v * 2 + 1, mid + 1, tr, l, r));
  51.     }
  52.     void update(ll v, ll tl, ll tr, ll l, ll r, ll x) {
  53.         push(v);
  54.         if (tl > r || tr < l) {
  55.             return;
  56.         }
  57.         if (tl >= l && tr <= r) {
  58.             mod[v] += x;
  59.             push(v);
  60.             return;
  61.         }
  62.         ll mid = (tl + tr) / 2;
  63.         update(v * 2, tl, mid, l, r, x);
  64.         update(v * 2 + 1, mid + 1, tr, l, r, x);
  65.         tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
  66.     }
  67.     ll get_max(ll l, ll r, ll n) {
  68.         return get(1, 0, n - 1, l, r);
  69.     }
  70.     void upd_seg(ll l, ll r, ll x, ll n) {
  71.         update(1, 0, n - 1, l, r, x);
  72.     }
  73. };
  74. signed main() {
  75. #ifdef _DEBUG
  76.     freopen("input.txt", "r", stdin);
  77.     freopen("output.txt", "w", stdout);
  78. #endif
  79.     ios_base::sync_with_stdio(false);
  80.     cin.tie(nullptr);
  81.     cout.tie(nullptr);
  82.     srand(time(NULL));
  83.     auto interval_indef = [&](ll& l, ll& r) {
  84.         //r -= 2;
  85.         l--, r--;
  86.     };
  87.     auto segment = [&](ll& l, ll& r) {
  88.         l--, r--;
  89.     };
  90.     ll n;
  91.     cin >> n;
  92.     vector<ll> a(n);
  93.     for (ll& i : a) {
  94.         cin >> i;
  95.     }
  96.     Segtree tree;
  97.     tree.init(n, a);
  98.     ll m;
  99.     cin >> m;
  100.     for (ll i = 0; i < m; i++) {
  101.         char indef;
  102.         cin >> indef;
  103.         if (indef == 'a') {
  104.             ll l, r, x;
  105.             cin >> l >> r >> x;
  106.             segment(l, r);
  107.             tree.upd_seg(l, r, x, n);
  108.         }
  109.         if (indef == 'm') {
  110.             ll l, r;
  111.             cin >> l >> r;
  112.             interval_indef(l, r);
  113.             ll ans = tree.get_max(l, r, n);
  114.             cout << ans << ' ';
  115.         }
  116.     }
  117. }
Advertisement
Add Comment
Please, Sign In to add comment