Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("03")
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- using namespace std;
- using namespace chrono;
- #define all(a) a.begin(), a.end()
- #define allr(a) a.rbegin(), a.rend()
- #define endl "\n"
- mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
- typedef long long ll;
- typedef long double ld;
- struct Segtree {
- const ll inf = 1e18;
- vector<ll>tree;
- vector<ll>mod;
- void build(ll v, ll tl, ll tr, vector<ll>& a) {
- if (tl == tr) {
- tree[v] = a[tl];
- return;
- }
- ll mid = (tl + tr) / 2;
- build(v * 2, tl, mid, a);
- build(v * 2 + 1, mid + 1, tr, a);
- tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
- }
- void init(ll n, vector<ll>& a) {
- tree.resize(4 * n, -inf);
- mod.resize(4 * n, 0);
- build(1, 0, n - 1, a);
- }
- void push(ll v) {
- tree[v] += mod[v];
- if (v * 2 + 1 > (ll)tree.size()) {
- mod[v] = 0;
- return;
- }
- mod[v * 2] += mod[v];
- mod[v * 2 + 1] += mod[v];
- mod[v] = 0;
- }
- ll get(ll v, ll tl, ll tr, ll l, ll r) {
- push(v);
- if (tl > r || tr < l) {
- return -inf;
- }
- if (tl >= l && tr <= r) {
- return tree[v];
- }
- ll mid = (tl + tr) / 2;
- return max(get(v * 2, tl, mid, l, r), get(v * 2 + 1, mid + 1, tr, l, r));
- }
- void update(ll v, ll tl, ll tr, ll l, ll r, ll x) {
- push(v);
- if (tl > r || tr < l) {
- return;
- }
- if (tl >= l && tr <= r) {
- mod[v] += x;
- push(v);
- return;
- }
- ll mid = (tl + tr) / 2;
- update(v * 2, tl, mid, l, r, x);
- update(v * 2 + 1, mid + 1, tr, l, r, x);
- tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
- }
- ll get_max(ll l, ll r, ll n) {
- return get(1, 0, n - 1, l, r);
- }
- void upd_seg(ll l, ll r, ll x, ll n) {
- update(1, 0, n - 1, l, r, x);
- }
- };
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- srand(time(NULL));
- auto interval_indef = [&](ll& l, ll& r) {
- //r -= 2;
- l--, r--;
- };
- auto segment = [&](ll& l, ll& r) {
- l--, r--;
- };
- ll n;
- cin >> n;
- vector<ll> a(n);
- for (ll& i : a) {
- cin >> i;
- }
- Segtree tree;
- tree.init(n, a);
- ll m;
- cin >> m;
- for (ll i = 0; i < m; i++) {
- char indef;
- cin >> indef;
- if (indef == 'a') {
- ll l, r, x;
- cin >> l >> r >> x;
- segment(l, r);
- tree.upd_seg(l, r, x, n);
- }
- if (indef == 'm') {
- ll l, r;
- cin >> l >> r;
- interval_indef(l, r);
- ll ans = tree.get_max(l, r, n);
- cout << ans << ' ';
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment