Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <cassert>
- #include <algorithm>
- #include <map>
- #include <cmath>
- #include <stack>
- #include <iomanip>
- #include <set>
- #include <deque>
- #include <queue>
- #include <ctime>
- using namespace std;
- typedef __int128 lll;
- typedef long long ll;
- typedef double ld;
- ll inf = 1e9, mod = 1e9 + 7;
- const int N = 1e6;
- #define all(a) a.begin(),a.end()
- #define _GLIBCXX_DEBUG
- ll a[N], u[N], tree[N];
- void build(ll l, ll r, ll v) {
- if (l == r) {
- tree[v] = a[l];
- return;
- }
- ll m = (l + r) / 2;
- build(l, m, v + v);
- build(m + 1, r, v + v + 1);
- tree[v] = max(tree[v + v], tree[v + v + 1]);
- }
- void push(ll l, ll r, ll v) {
- if (!u[v])
- return;
- tree[v] += u[v];
- if (l == r) {
- u[v] = 0;
- return;
- }
- u[v + v] += u[v];
- u[v + v + 1] += u[v];
- u[v] = 0;
- }
- void change(ll l, ll r, ll v, ll la, ll ra, ll x) {
- push(l, r, v);
- if (l > ra || r < la)
- return;
- if (l >= la && r <= ra) {
- u[v] += x;
- push(l, r, v);
- return;
- }
- ll m = (l + r) / 2;
- change(l, m, v + v, la, ra, x);
- change(m + 1, r, v + v + 1, la, ra, x);
- tree[v] = max(tree[v + v], tree[v + v + 1]);
- }
- ll ans(ll l, ll r, ll v, ll la, ll ra) {
- push(l, r, v);
- if (l > ra || r < la)
- return 0;
- if (l >= la && r <= ra)
- return tree[v];
- ll m = (l + r) / 2;
- return max(ans(l, m, v + v, la, ra), ans(m + 1, r, v + v + 1, la, ra));
- }
- int main() {
- #ifdef anime
- freopen("input1.txt", "r", stdin);
- freopen("outpu1.txt", "w", stdout);
- #endif
- srand(time(nullptr));
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- ll n, k, i;
- cin >> n;
- for (i = 0; i < n; i++)
- cin >> a[i + 1];
- build(1, n, 1);
- cin >> k;
- while (k--) {
- char c;
- cin >> c;
- ll x, y;
- cin >> x >> y;
- if (c == 'a') {
- ll z;
- cin >> z;
- change(1, n, 1, x, y, z);
- } else
- cout << ans(1, n, 1, x, y) << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
