Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define INF 1e9
- long long t[400004], val[400004], a[100000];
- void build(int v, int lt, int rt) {
- if (lt == rt)
- t[v] = a[lt];
- else {
- int mt=(lt+rt)/2;
- build(2*v, lt, mt);
- build(2*v+1, mt+1, rt);
- t[v] = max(t[2*v], t[2*v+1]);
- }
- }
- void push(int v) {
- if (val[v] > 0) {
- t[2*v] += val[v];
- t[2*v+1] += val[v];
- val[2*v] = val[2*v+1] = val[v];
- val[v] = 0;
- }
- }
- int get(int v, int lt, int rt, int l, int r) {
- if (l > r)
- return -INF;
- if (l==lt && r==rt)
- return t[v];
- push(v);
- int mt=(lt+rt)/2;
- return max(
- get(2*v, lt, mt, l, min(mt, r)),
- get(2*v+1, mt+1, rt, max(l, mt+1), r)
- );
- }
- void update(int v, int lt, int rt, int l, int r, int x) {
- if (l > r)
- return;
- if (l==lt && r==rt) {
- t[v] += x;
- val[v] = x;
- return;
- }
- push(v);
- int mt=(lt+rt)/2;
- update (v*2, lt, mt, l, min(r, mt), x);
- update (v*2+1, mt+1, rt, max(l, mt+1), r, x);
- t[v] = max(t[2*v], t[2*v+1]);
- }
- int main() {
- int n=0; cin >> n;
- for (int i=0; i<n; i++)
- cin >> a[i];
- build(1, 0, n-1);
- int m=0; cin >> m;
- vector<long long> ans;
- for (int i=0; i<m; i++) {
- char ch; cin >> ch;
- if (ch == 'm') {
- int l=0, r=0; cin >> l >> r;
- ans.push_back(get(1, 0, n-1, l-1, r-1));
- } else {
- int l=0, r=0, x=0; cin >> l >> r >> x;
- update(1, 0, n-1, l-1, r-1, x);
- }
- }
- for (long long i: ans)
- cout << i << ' ';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement