记录编号	600465	评测结果	AAAAAAAAAA
题目名称	4141.愈加善良的希望	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	2.857 s
提交时间	2025-05-04 16:27:25	内存使用	5.01 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pir pair<ll,ll>
#define ls first
#define rs second
#define mp make_pair
#define mod
#define MAXN 50010
#define V 50000ll
#define len 230ll
#define qmod(x) (x>mod?x-mod:x)
inline ll read(){
    ll x = 0,f = 1;
    char c = getchar();
    while(c < '0'||c > '9'){
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0'&&c <= '9'){
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}
ll tag[MAXN],k[MAXN],L[MAXN],R[MAXN];
ll tot,n,m,s[MAXN],pos[MAXN];


struct node_conv{
    pir t[len + 10];
    ll tp;
    bool cmp(pir a, pir b, pir c){
        return ((b.rs - a.rs) * (c.ls - b.ls) <= (b.ls - a.ls) * (c.rs - b.rs));
    }

    void insert(pir val){
        while(tp > 1){
            if(cmp(t[tp - 1], t[tp], val))-- tp;
            else break;
        }
        ++ tp;
        t[tp] = val;
    }

    ll get(ll k){
        ll l = 1,r = tp;
        while(r > l){
            ll mid = (l + r) >> 1;
            if((t[mid + 1].rs - t[mid].rs) > k * (t[mid + 1].ls - t[mid].ls))l = mid + 1;
            else r = mid;
        }
        return t[l].rs - t[l].ls * k;
    }

}conv[len + 10];


void make(ll now){
    conv[now].tp = 0;
    for(int i = L[now];i <= R[now]; ++i){
        s[i] = s[i] + (i - L[now]) * k[now] + tag[now];
        conv[now].insert(mp(i - L[now], s[i]));
    }
    tag[now] = k[now] = 0;
}


void add(ll l, ll r, ll val){
    ll p = pos[l],q = pos[r];
    if(p == q){
        for(int i = l;i <= r; ++i)s[i] += val;
        // cout << s[3] << endl;
        make(p);
    }else{
        for(int i = l;i <= R[p]; ++i)s[i] += val;
        for(int i = L[q];i <= r; ++i)s[i] += val;
        make(p), make(q);
        for(int i = p + 1;i < q; ++i){
            // make(i);
            tag[i] += val;
        }
    }
}


void modify(ll l, ll r, ll val){
    ll p = pos[l],q = pos[r];
    if(p == q){
        for(int i = l;i <= r; ++i)s[i] += (i - l + 1) * val;
        make(p);
    }else{
        for(int i = l;i <= R[p]; ++i)s[i] += (i - l + 1) * val;
        for(int i = L[q];i <= r; ++i)s[i] += (i - l + 1) * val;
        // cout << "!3: " <<s[3] << endl;
        make(p), make(q);
        // cout << ":3 " << s[3] << endl;
        for(int i = p + 1;i < q; ++i){
            // make(i);
            tag[i] += (L[i] - l + 1) * val;
            k[i] += val;
        }
    }
}


ll query(ll l, ll r){
    ll p = pos[l], q = pos[r];
    ll res = -1e18;
    if(p == q){
        make(p);
        for(int i = l;i <= r; ++i){
            res = max(res, s[i]);
        }
    }else{
        make(p), make(q);
        for(int i = l;i <= R[p]; ++i){
            res = max(res, s[i]);
        }
        for(int i = L[q];i <= r; ++i){
            res = max(res, s[i]);
        }
        for(int i = p + 1;i < q; ++i){
            // make(i);
            res = max(res, conv[i].get(-k[i]) + tag[i]);
            // cout << i << " " <<  conv[i].get(-k[i]) << endl;
        }
    }
    return res;
}

int main(){
    // freopen("data.out", "r", stdin);
    // freopen("SP.out", "w", stdout);
    n = read();
    tot = (n - 1) / len + 1;
    for(int i = 1;i <= tot; ++i){
        L[i] = R[i - 1] + 1;
        R[i] = min(i * len, n);
        for(int j = L[i];j <= R[i]; ++j)pos[j] = i;
    }
    for(int i = 1;i <= n; ++i){
        s[i] = s[i - 1] + read();
        // cout << s[i] << " ";
    }
    // cout << endl;
    m = read();
    for(int i = 1;i <= tot; ++i)make(i);
    for(int i = 1;i <= m; ++i){
        ll type = read();
        if(type == 1){
            ll l = read(),r = read();
            printf("%lld\n", query(l,r));
        }else{
            ll l = read(),r = read(),val = read();
            if(r > l)modify(l, r - 1, val);
            add(r, n, val * (r - l + 1));
        }
    }
    return 0;
}			

/*
5
238 -9622 5181 202 -6943
6
1 3 4
0 5 5 4846
1 3 5
1 3 3
0 3 5 -7471
1 3 3
*/