935F, C++ (gcc) - rextester

Language: Layout:

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define mod 1000000007

using namespace std;

typedef long long ll;

#define pii pair<ll, ll>

ll n, seg[300001], seg2[300001], seg4[300001], a[100001], diff[100001], frwdDiff[100001];

set<int> localMax, localMin;

ll ans = 0;

ll lazy[300001] = {0};

void build(ll l, ll r, ll i){
    if(l == r){
        seg[i] = diff[l];
        seg2[i] = a[l];
        seg4[i] = frwdDiff[l];
        return;
    }
    ll mid = (l+r)/2;
    build(l, mid, i*2+1);
    build(mid+1, r, i*2+2);

seg[i] = max(seg[i*2+1], seg[i*2+2]);
    //seg2[i] = seg3[i*2+1] | seg3[i*2+2];
    seg4[i] = max(seg4[i*2+1], seg4[i*2+2]);
}

ll query(ll l, ll r, ll i, ll x, ll y){
    if(r < x || l > y) return -mod;
    if(l >= x && r <= y) return seg[i];
    ll mid = (l+r)/2;
    return max(query(l, mid, i*2+1, x, y), query(mid+1, r, i*2+2, x, y));
}

ll query4(ll l, ll r, ll i, ll x, ll y){
    if(r < x || l > y) return -mod;
    if(l >= x && r <= y) return seg4[i];
    ll mid = (l+r)/2;
    return max(query4(l, mid, i*2+1, x, y), query4(mid+1, r, i*2+2, x, y));
}

void update(ll l, ll r, ll i, ll pos){
    if(l == r){
        seg[i] = diff[l];
        return;
    }
    ll mid = (l+r)/2;
    if(mid >= pos) update(l, mid, i*2+1, pos);
    else update(mid+1, r, i*2+2, pos);
    seg[i] = max(seg[i*2+1], seg[i*2+2]);
}

void update_lazy(ll l, ll r, ll i){
    if(!lazy[i]) return;
    if(l != r){
        lazy[i*2+1] += lazy[i];
        lazy[i*2+2] += lazy[i];
    }
    else a[l] += lazy[i];
    lazy[i] = 0;
}

void update2(ll l, ll r, ll i, ll x, ll y, ll val){
    update_lazy(l, r, i);
    if(r < x || l > y) return;
    if(l >= x && r <= y){
        lazy[i] = val;
        update_lazy(l, r, i);
        return;
    }
    ll mid = (l+r)/2;
    update2(l, mid, i*2+1, x, y, val);
    update2(mid+1, r, i*2+2, x, y, val);
}

ll query2(ll l, ll r, ll i, ll pos){
    update_lazy(l, r, i);
    if(l == r) return a[l];
    int mid = (l+r)/2;
    if(mid >= pos) return query2(l, mid, i*2+1, pos);
    return query2(mid+1, r, i*2+2, pos);
}

void update4(ll l, ll r, ll i, ll pos){
    if(l == r){
        seg4[i] = frwdDiff[l];
        return;
    }
    ll mid = (l+r)/2;
    if(mid >= pos) update4(l, mid, i*2+1, pos);
    else update4(mid+1, r, i*2+2, pos);
    seg4[i] = max(seg4[i*2+1], seg4[i*2+2]);
}

ll query_(ll l, ll r, ll x){
    if(l == r){
        query2(0, n-1, 0, l-1);
        query2(0, n-1, 0, l+1);
        query2(0, n-1, 0, l);
        ll prv = abs(a[l] - a[l-1]) + abs(a[l] - a[l+1]);
        ll t = abs(a[l] + x - a[l-1]) + abs(a[l] + x - a[l+1]);
        return (t - prv);
    }
    if(l+1 == r){
        query2(0, n-1, 0, l-1);
        query2(0, n-1, 0, l+1);
        query2(0, n-1, 0, l);
        query2(0, n-1, 0, r+1);
        
        ll prv1 = abs(a[l] - a[l-1]) + abs(a[l] - a[l+1]), prv2 = abs(a[r] - a[r+1]) + abs(a[r] - a[r-1]);
        ll t1 = abs(a[l]+x - a[l-1]) + abs(a[l]+x - a[l+1]), t2 = abs(a[r] + x - a[r+1]) + abs(a[r]+x - a[r-1]);
        return max(t1 - prv1, t2 - prv2);
    }

ll m = *localMax.upper_bound(l-1);
    if(m <= r && m >= l) return (x*2);
    int y = *localMin.upper_bound(l-1);
    if(y <= r && y >= l){
        query2(0, n-1, 0, y-1);
        query2(0, n-1, 0, y+1);
        query2(0, n-1, 0, y);
        
        ll t = -mod;
        if(l <= (y-1)) t = max(t, query4(0, n-1, 0, l, y-1));
        if(r >= (y+1)) t = max(t, query(0, n-1, 0, y+1, r));
        ll val1 = max((ll)0, (t+x)*2);
        ll a1 = a[y-1], b = a[y], c = a[y + 1];
        ll val = max(x - (c - b), (ll)0) - min(x, (a1-b));
        val *= 2;
        return max(val, val1);
    }
    
    query2(0, n-1, 0, l+1);
    query2(0, n-1, 0, l);
    if(a[l] >= a[l+1]) return max((ll)0, (query4(0, n-1, 0, l, r) + x)*2);
    return max((ll)0, (query(0, n-1, 0, l, r) + x)*2);
}

void update_(ll l, ll r, ll val){
    query2(0, n-1, 0, l-1);
    query2(0, n-1, 0, l);
    query2(0, n-1, 0, l+1);
    query2(0, n-1, 0, r+1);
    query2(0, n-1, 0, r);
    query2(0, n-1, 0, r-1);
    if(l - 2 >= 0) query2(0, n-1, 0, l-2);
    if(r+2 < n) query2(0, n-1, 0, r+2);

ans -= abs(a[l-1] - a[l]);
    ans -= abs(a[r] - a[r+1]);
    ans += abs(a[l-1] - a[l] - val);
    ans += abs(a[r+1] - a[r] - val);
    
    const ll x = val;
    if(localMax.count(l-1) > 0 && (a[l] + x) > a[l-1]) localMax.erase(l-1);
    if(localMax.count(r+1) > 0 && (a[r] + x) > a[r+1]) localMax.erase(r+1);
    if(localMin.count(l) > 0 && (a[l] + x) >= a[l-1]) localMin.erase(l);
    if(localMin.count(r) > 0 && (a[r] + x) >= a[r+1]) localMin.erase(r);
    
    ll nxt = (l+1 <= r)? a[l+1] + x : a[l+1];
    if(localMax.count(l) == 0 && (a[l] + x) >= a[l-1] && (a[l] + x) >= nxt) localMax.insert(l);
    ll prv = (r-1 >= l)? a[r-1] + x : a[r-1];
    if(localMax.count(r) == 0 && (a[r] + x) >= a[r+1] && (a[r] + x) >= prv) localMax.insert(r);
    
    if(r+2 < n && localMin.count(r+1) == 0 && (a[r] + x) > a[r+1] && a[r+1] < a[r+2]) localMin.insert(r+1);
    if(l-2>= 0 && localMin.count(l-1) == 0 && (a[l] + x) > a[l-1] && a[l-1] < a[l-2]) localMin.insert(l-1);
    
    diff[l-1] -= val;
    update(0, n-1, 0, l-1);
    diff[r] += val;
    update(0, n-1, 0, r);

frwdDiff[l] += val;
    update4(0, n-1, 0, l);
    frwdDiff[r+1] -= val;
    update4(0, n-1, 0, r+1);

update2(0, n-1, 0, l, r, val);
}

void print(){
    set<int> :: iterator it;
    cout << "localMin : ";
    for(it = localMin.begin(); it != localMin.end(); it++)
        cout << *it << " ";
    cout << endl << "localMax : ";
    for(it = localMax.begin(); it != localMax.end(); it++)
        cout << *it << " ";
    cout << endl;
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

cin >> n;
    for(ll j = 0; j < n; j++)
        cin >> a[j];
    for(ll j = 0; j < n-1; j++){
        diff[j] = a[j] - a[j+1];
        ans += abs(diff[j]);
    }
    diff[n-1] = a[n-1];

for(ll j = n-1; j > 0; j--)
        frwdDiff[j] = a[j] - a[j-1];
    frwdDiff[0] = a[0];

for(ll j = 1; j < n-1; j++){
        if(a[j] >= a[j-1] && a[j] >= a[j+1]) localMax.insert(j);
        if(a[j] < a[j-1] && a[j] < a[j+1]) localMin.insert(j);
    }

build(0, n-1, 0);

ll q;
    cin >> q;
    while(q--){
        ll t, l, r, val;
        cin >> t >> l >> r >> val;
        if(t == 1) cout << (ans + query_(l-1, r-1, val)) << endl;
        else update_(l-1, r-1, val);
        //print();
    }
    return 0;
}

Show compiler warnings [ + ] Compiler args [ - ] Show input
Compilation time: 1.94 sec, absolute running time: 0.13 sec, cpu time: 0.06 sec, memory peak: 3 Mb, absolute service time: 2,08 sec