Polynomial range update - Query max (CHT + sqrt decomposition)

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e5, block = 330;
struct CHT
{
    vector<long double> inter;
    vector<long long> A, B;
    void Clear()
    {
        inter.clear();
        A.clear();
        B.clear();
    }
    long double intersect(long long x1, long long y1, long long x2, long long y2)
    {
        return (long double)(y2 - y1)/(x1 - x2);
    }
    void add(long long a, long long b)
    {
        while(inter.size() > 1 && intersect(a, b, A.back(), B.back()) <= intersect(a, b, A[A.size() - 2], B[B.size() - 2]))
        {
            inter.pop_back();
            A.pop_back();
            B.pop_back();
        }
        if (inter.empty())
        {
            inter.push_back(-1e18);
        }
        else
        {
            inter.push_back(intersect(a, b, A.back(), B.back()));
        }
        A.push_back(a);
        B.push_back(b);
    }
    long long get(long long x)
    {
        int i = upper_bound(inter.begin(), inter.end(), (long double)x) - inter.begin() - 1;
        return A[i] * x + B[i];
    }
} dp[330];
long long cur[N + 1], lazy[330], a[330];
int n;
void add(int l, int r, long long x, long long y, int st)
{
    int bl = (l + block - 1)/block, br = (r + block - 1)/block;
    if (bl == br)
    {
        for (int i = (bl - 1) * block + 1; i <= min(n, bl * block); ++ i)
        {
            cur[i] += lazy[bl] + 1LL * i * a[bl];
        }
        lazy[bl] = a[bl] = 0;
        for (int i = l; i <= r; ++ i)
        {
            cur[i] += x + 1LL * (i - st) * y;
        }
        dp[bl].Clear();
        for (int i = (bl - 1) * block + 1; i <= min(n, bl * block); ++ i)
        {
            dp[bl].add(i, cur[i]);
        }
        return ;
    }
    for (int i = bl + 1; i < br; ++ i)
    {
        lazy[i] += x - 1LL * st * y;
        a[i] += y;
    }
    add(l, bl * block, x, y, st);
    add((br - 1) * block + 1, r, x, y, st);
}
long long cal(int i)
{
    int bl = (i + block - 1)/block;
    return cur[i] + a[bl] * i + lazy[bl];
}
long long get(int l, int r)
{
    int bl = (l + block - 1)/block, br = (r + block - 1)/block;
    long long ret = 0;
    if (bl == br)
    {
        for (int i = l; i <= r; ++ i)
        {
            ret = max(ret, cal(i));
        }
        return ret;
    }
    for (int i = bl + 1; i < br; ++ i)
    {
        ret = max(ret, dp[i].get(a[i]) + lazy[i]);
    }
    ret = max(ret, get(l, bl * block));
    ret = max(ret, get((br - 1) * block + 1, r));
    return ret;
}
void read()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> cur[i];
    }
    for (int i = 1; i <= (n + block - 1)/block; ++ i)
    {
        for (int j = (i - 1) * block + 1; j <= min(n, i * block); ++ j)
        {
            dp[i].add(j, cur[j]);
        }
    }
}
void solve()
{
    int q;
    cin >> q;
    while(q--)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int l, r;
            cin >> l >> r;
            cout << get(l, r) << '\n';
        }
        else
        {
            int l, r;
            long long x, y;
            cin >> l >> r >> x >> y;
            add(l, r, x, y, l);
        }
        /*for (int i = 1; i <= n; ++ i)
        {
            cerr << cal(i) << ' ';
        }
        cerr << '\n';*/
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}