再续前缘

大力分块2

又来找虐

背景

可以见大力分块，这是它的续

开始之前，大喊一声：我爱lxl！

第六分块

「深浅值藏的第六分块」（让luogu臭名昭著的研究珂学最佳方式）

末日时在做什么？有没有空？可以来拯救吗？

维护一个序列，支持两种操作：把区间 $[l, r]$ 加 $x$ ；查询区间 $[l, r]$ 最大子段和， $n, m \le 10^5$ ，任意时刻 $|a| \le 2 \times 10^9$ ， $1s, 64MB$

下面是我脑内的处理过程：

dfs预处理

额……前置知识有点多，等我去递归式学习一手

尴尬了，递归了一会发现自己爆栈了……我太弱了！！！

但硬着头皮想（he）一（ti）想（jie）吧

弱化版

先想一个弱化的问题：没有修改，求区间最大子段和，这就是猫树的板子（线段树也行），不管了

稍微强一点的：全局修改，求区间最大子段和

猫树直接爆炸，考虑线段树，线段树上维护 $sum, suf, pre, as$ ，表示区间和、区间最大后缀和、区间最大前缀和、区间最大子段和，在全局加的情况下，我们如何维护这几个数字呢？

$sum$ 直接加即可

$pre$ 可以维护一个凸函数 $f(x)$ 表示长度为 $x$ 的前缀和，最大化 $pre = f(x) + d * x$ ，改写为 $f(x) = d * x + pre$ ， $f(x)$ 可以 $O(n)$ 求，然后斜率优化，二分凸包最大化截距即可； $suf$ 同理维护 $g(x)$

$as$ 也尝试维护一个凸函数 $h(x)$ 表示长度为 $x$ 的大子段和，也去凸包二分……但 $h(x)$ 可没法 $O(n)$ 求啊

考虑用下一层节点的信息，取子节点的 $g_l, f_r, h_l, h_r$ ，有 $h(x + y) = \max(h_l(x + y), h_r(x + y), g_l(x) + f_r(y))$ ，前两项直接继承，第三项闵可夫斯基和解决，都是线性的

终于，我们有了 $O(n \log n)$ 建树，求答案时对线段树每一个凸包二分，是 $O(\log^2 n)$

TLE版

好，那区间修改怎么办？我们上面的做法可不支持区间修改呀！

考虑分块暴力，对每一块建一棵线段树，整块直接修改，散点直接重构，查询时整块在根节点二分凸包，散点就当线段树查询

设块长为 $B$ ，整块修改 $O(1)$ ，散点重构 $O(B \log B)$ ，整块查询 $O(\log B)$ ，散点查询 $O(\log^2 B)$ ，每次操作最多涉及 $\frac{n}{B}$ 个整块和两个散点，取 $B = \sqrt{n}$ ，时间复杂度为 $O(m \sqrt{n} \log \sqrt{n})$ ，还有个大常数，这不T上天，而且空间也上天了

空间可以离线逐块处理，时间上，一看是lxl的题，当然选择保留 $\sqrt{n}$ ，优化掉 $\log \sqrt{n}$ ，发现复杂度的 $\log$ 存在于两个地方：散点的重构和整块的查询（散点查询每次操作最多做两次，不是瓶颈）

散点优化

重构整棵线段树当然是 $B \log B$ ，但真的需要重构整棵吗？

我们重构的原因是本题中线段树只支持整体修改，不支持某一段修改，那么，当我们递归到某一段 $[l ,r]$ 已经完全被修改区间包含，为什么不直接打懒标记呢？

为了让这个懒标记区别于原来的懒标记，我们把它打在凸包上不下放，取凸包内节点的时候考虑叠加的正比例函数对点的位置的影响即可，而把原来的不打在树上，开一个变量单独存

因为每层只有一个节点（最左or最右）没完全被包含，所以每层只有 $O(1)$ 的节点被重构，这层的 $1$ 个节点对应下面的 $2$ 个，再下面 $4$ 个……等比数列求和，总的是 $O(B)$ 的

整块优化

首先，整体查询一定是提取线段树根上面那个凸包，而因为整体修改的标记在一个全块共用的变量上，所以根上一定是没有标记的；其次由于我们逐块处理，两个修改间的查询顺序是任意的，综上，我们考虑把所有查询按照查询时整体加标记的值升序排序，然后转换成整体加只加正数（先把标记减了就好）

这里我不是很李姐，巨佬们说由于区间加的都是正数，可以维护一个当前的最优决策点 $p$ ，决策点只会向右移动，暴力的向右爬一下即可，散点修改重构凸包的时候，直接把指针重置

这样处理询问的均摊复杂度是 $O(B)$ ，简证（口胡）：

定义一个块的 $E$ 为根上面的指针距离块右端点的距离，显然最开始的时候，所以块的 $E$ 和 $sum_E = n$ ，每次操作，最多有 $2$ 个散点所在块被重构，导致这两个块指针重置， $sum_E$ 增加 $2B$ ，所以总的 $sum_E$ 在过程中增加最多 $2mB$ ，而让 $sum_E$ 减少的唯一方法就是爬指针，每次减少至少 $1$ ，当 $sum_E = 0$ 时指针显然不会再爬（都到了右端点，不能再往右了），所以指针最多移动 $\frac{n + 2mB}{1}$ 次，时间为 $O(mB)$ ，均摊到每一次操作，就是 $O(B)$

一个小点：排序时用基数排序，把总排序时间从 $O(m B \log m)$ 优化到 $O(mB)$

到此为止，散点修改 $O(B)$ ，散点查询 $O(\log^2 B)$ ，整块修改 $O(1)$ ，整块查询 $O(B)$ （这里整块查询指一次操作中的所有整块时间和），取 $B = \sqrt{n}$ ，时间复杂度为 $O(m \sqrt{n})$ ，似乎行了？可能吗，这可是lxl啊

卡常

1. 快读快输
2. 基数排序用松氏基排，个数较小时用快排
3. 维护凸包时别开 vector ，自己分配内存（就像我闵可夫斯基和博客里写的一样）
4. 由于在块长不变的时候内存分配情况一定不会变，所以只需要在第一个和最后一块分配一下内存，不需要每次都重新分配
5. 最终优化，调块长吧，多试几次

受苦

啊啊啊不想打啊！

• $2022/1/26$ $7:30$ 开始本题
• $2022/1/26$ $1:27$ 开打
• $2022/1/26$ $16:30$ 打完开调
• $2022/1/26$ $18:17$ 过样例了
• $2022/1/26$ $18:30$ 第一次提交，TLE + RE $0pts$
• $2022/1/26$ $19:18$ 改过RE了（二分打挂了），TLE + WA $0pts$
• $2022/1/26$ $19:33$ 不WA了，TLE $0pts$
• $2022/1/26$ $19:33$ 本着宁WA不T的原则卡块长，发现当 $B = 1148$ 时最好（然鹅还是TLE一个点）WA $0pts$
• $2022/1/26$ $21:56$ 发现把 $bn$ 打成 $n$ 了，改了后TLE $80pts$ ，啊啊啊，我的打法常数大了！
• $2022/1/27$ $9:45$ 把网上能找到的代码（包括所有的题解）都交了一遍，全TLE（好像lxl加强了），心态爆炸
• $2022/1/27$ $10:00$ 猛然发现一篇分类讨论的 $36pts$ 的代码刚好AC了我TLE的点（他特别猛，就手玩），于是决定高素质……
• $2022/1/27$ $10:37$ 高素质过了！决定加点注释，压压行
• $2022/1/27$ $11:08$ 搞定

代码

超长警告！不压行 $737$ 行，压了后 $649$ 行！lxl太毒瘤了

/*
2022/1/27 11:08
by Dyd
由于代码很长,稍微压了一下行
*/
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define LL long long
#define IL inline
#define Max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) < (y) ? (x) : (y))
#define got(x, len) (((x) - 1) / (len) + 1)
#define LB(x, len) (((x) - 1) * (len) + 1)
#define RB(x, len) Min(((x) * (len)), n)
using namespace std;
namespace Fast
{
    const int L = (1 << 20) + 5;
    char buf[L], out[L], *iS, *iT;
    int l = 0;
    #define gh() (iT == iS ? iT = (iS = buf) + fread(buf, 1, L, stdin), (iT == iS ? EOF : *iS++) : *iS++)
    template <class T>
    IL void read(T &x)
    {
        x = 0;
        char ch = gh(), t = 0;
        while (ch < '0' || ch > '9')
            t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9')
            x = x * 10 + (ch ^ 48), ch = gh();
        if (t)
            x = -x;
    }
    IL void flus() { fwrite(out, 1, l, stdout), l = 0; }
    IL void putc(char x) { out[l++] = x; }
    template <class T>
    IL void write(T x)
    {
        if (x < 0)
            putc('-'), x = -x;
        if (x > 9)
            write(x / 10);
        out[l++] = x % 10 + 48;
    }
}
using Fast::flus;
using Fast::putc;
using Fast::read;
using Fast::write;
const int B = 1148, N = 1e5 + B + 5, R = 256, Bit = 8;
const LL MINF = -0x3f3f3f3f3f3f3f3f;
int a[N], n, m;
struct Question
{
    int op = 0, l = 0, r = 0;
    LL v = 0;
} que[N];
//我的程序(80pts,最后一个点会TLE)
namespace My
{
    //bl,br,pos卡常,记录LB,RB,got;tot:分配空间
    int bl[N / B + 5], br[N / B + 5], pos[N], tot;
    struct Point
    {
        LL x, y;
        IL Point operator + (const Point &b) const { return {x + b.x, y + b.y}; }
        IL Point operator - (const Point &b) const { return {x - b.x, y - b.y}; }
        IL bool operator <= (const Point &b) const { return x * b.y >= y * b.x; }
    } pool[N];
    struct Hull
    {
        Point *vc;
        int si, mxid;
        LL tag;
        IL Point operator [] (const int x) { return {vc[x].x, vc[x].y + tag * vc[x].x}; }
        IL void ins(Point x) { vc[x.x].y = Max(vc[x.x].y, x.y); }
        IL void push_back(Point x) { vc[si++] = x; }
        IL void prev(int len) //预留len的空间(赋为MINF以待跟新)
        {
            vc[0] = {0, 0}, si = len + 1, tag = 0;
            for (int i = 1; i <= len; ++i) vc[i] = {i, MINF};
        }
        IL void jarvis() //求凸包
        {
            if (si <= 2) return;
            int top = 1;
            for (int i = 2; i < si; ++i)
            {
                if (vc[i].y == MINF) continue;
                while (top >= 1 && (vc[top] - vc[top - 1]) <= (vc[i] - vc[top - 1])) --top;
                vc[++top] = vc[i];
            }
            si = top + 1, tag = 0;
        }
        IL bool check(int x, LL addv) { return (vc[x + 1].x - vc[x].x) * (tag + addv) + vc[x + 1].y - vc[x].y > 0; }
        IL LL maxv(LL addv)
        {
            while (mxid < si - 1 && check(mxid, addv)) ++mxid;
            return vc[mxid].x * (tag + addv) + vc[mxid].y;
        }
        IL LL bs(LL addv) //凸包上二分
        {
            int l = -1, r = si - 1, mid;
            for (mid = l + r >> 1; l < r - 1; mid = l + r >> 1)
                if (check(mid, addv)) l = mid;
                else r = mid;
            mxid = r;
            return vc[mxid].x * (tag + addv) + vc[mxid].y;
        }
    };
    struct Ans
    {
        LL pre, suf, as, sum;
        IL Ans operator + (const Ans &b) const { return {Max(pre, sum + b.pre), Max(suf + b.sum, b.suf), Max(Max(as, b.as), suf + b.pre), sum + b.sum}; }
    } ans[N];
    struct LineTree
    {
        Hull pre[B << 2], suf[B << 2], as[B << 2];
        LL sum[B << 2], tag[B << 2];
        #define lc (u << 1)
        #define rc (u << 1 | 1)
        #define Mid ((l + r) >> 1)
        IL void prev(int u, int l, int r) //预分配空间
        {
            pre[u].vc = pool + tot, tot += r - l + 3;
            suf[u].vc = pool + tot, tot += r - l + 3;
            as[u].vc = pool + tot, tot += r - l + 3;
            if (l == r) return;
            int mid = Mid;
            prev(lc, l, mid), prev(rc, mid + 1, r);
        }
        IL void pre_suf_merge(Hull &c, Hull &a, Hull &b, Point addb) //普通合并
        {
            for (int i = 0, t = a.si; i < t; ++i) c.push_back(a[i]);
            for (int i = 0, t = b.si; i < t; ++i) c.push_back(addb + b[i]);
            c.jarvis();
        }
        IL void minkowski(Hull &c, Hull &a, Hull &b) //闵可夫斯基和
        {
            int i = 0, j = 0, sa = a.si - 1, sb = b.si - 1;
            for (c.ins(a[i] + b[j]); i < sa && j < sb; c.ins(a[i] + b[j])) a[i + 1] - a[i] <= b[j + 1] - b[j] ? ++j : ++i;
            while (i < sa) c.ins(a[++i] + b[j]);
            while (j < sb) c.ins(a[i] + b[++j]);
        }
        IL void up(int u, int l, int r)
        {
            int mid = Mid;
            pre_suf_merge(pre[u], pre[lc], pre[rc], {mid - l + 1, sum[lc]});
            pre_suf_merge(suf[u], suf[rc], suf[lc], {r - mid, sum[rc]});
            as[u].prev(r - l + 1);
            for (int i = 0, t = as[lc].si; i < t; ++i) as[u].ins(as[lc][i]);
            for (int i = 0, t = as[rc].si; i < t; ++i) as[u].ins(as[rc][i]);
            minkowski(as[u], suf[lc], pre[rc]);
            as[u].jarvis();
            pre[u].mxid = suf[u].mxid = as[u].mxid = 0;
            sum[u] = sum[lc] + sum[rc];
        }
        //添加标记,同时修改
        IL void add(int u, int l, int r, LL d) { tag[u] += d, pre[u].tag += d, suf[u].tag += d, as[u].tag += d, sum[u] += d * (r - l + 1); }
        IL void down(int u, int l, int r)
        {
            if (l == r || !tag[u]) return;
            int mid = Mid;
            add(lc, l, mid, tag[u]), add(rc, mid + 1, r, tag[u]);
            tag[u] = 0;
        }
        IL void build(int u, int l, int r, int bid)
        {
            if (l == r)
            {
                sum[u] = a[l + bl[bid] - 1];
                pre[u].push_back({0, 0}), pre[u].push_back({1, sum[u]});
                suf[u].push_back({0, 0}), suf[u].push_back({1, sum[u]});
                as[u].push_back({0, 0}), as[u].push_back({1, sum[u]});
                return;
            }
            int mid = Mid;
            build(lc, l, mid, bid), build(rc, mid + 1, r, bid);
            up(u, l, r);
        }
        IL void clear(int u, int l, int r)
        {
            pre[u].si = suf[u].si = as[u].si = 0;
            pre[u].mxid = suf[u].mxid = as[u].mxid = 0;
            pre[u].tag = suf[u].tag = as[u].tag = 0;
            tag[u] = 0;
            if (l == r) return;
            int mid = Mid;
            clear(lc, l, mid), clear(rc, mid + 1, r);
        }
        IL void change(int u, int l, int r, int ql, int qr, LL d) //散点修改
        {
            if (l == ql && r == qr) return add(u, l, r, d);
            down(u, l, r);
            int mid = Mid;
            if (qr <= mid) change(lc, l, mid, ql, qr, d);
            else if (ql > mid) change(rc, mid + 1, r, ql, qr, d);
            //注意这里ql,qr改变了
            else change(lc, l, mid, ql, mid, d), change(rc, mid + 1, r, mid + 1, qr, d);
            pre[u].si = suf[u].si = as[u].si = 0;
            up(u, l, r);
        }
        //整块询问
        IL Ans query(int l, int r, LL addv) { return {pre[1].maxv(addv), suf[1].maxv(addv), as[1].maxv(addv), sum[1] + (r - l + 1) * addv}; }
        IL Ans ask(int u, int l, int r, int ql, int qr, LL addv) //散点询问
        {
            if (l == ql && r == qr) return u == 1 ? query(ql, qr, addv) : (Ans){pre[u].bs(addv), suf[u].bs(addv), as[u].bs(addv), sum[u] + (qr - ql + 1) * addv};
            down(u, l, r);
            int mid = Mid;
            if (qr <= mid) return ask(lc, l, mid, ql, qr, addv);
            else if (ql > mid) return ask(rc, mid + 1, r, ql, qr, addv);
            else return ask(lc, l, mid, ql, mid, addv) + ask(rc, mid + 1, r, mid + 1, qr, addv);
        }
    };
    struct QuestionForBlock
    {
        int l = 0, r = 0, id = 0;
        LL v = 0, typ = 0;
        IL bool operator<(const QuestionForBlock &b) const { return v < b.v; }
    };
    struct Block
    {
        LineTree lt;
        //cnt,tmp,val,valt都是基数排序用的,为了卡常在这里定
        int bid, bn, bm, cnt[R];
        QuestionForBlock bq[N], tmp[N];
        LL tag, valt[N], val[N];
        //整体修改
        IL void modify(LL d) { tag += d; }
        IL void change(int l, int r, LL d) //散点修改
        {
            if (d == 0) return;
            if (l == 1 && r == bn) return tag += d, void();
            bq[bm++] = {l, r, 0, tag, d};
        }
        //整体查询
        IL void query(int l, int r, int id) { bq[bm++] = {l, r, id, tag, 0}; }
        #define geted(x, d) (((x) >> ((d)*Bit)) & (R - 1))
        IL void radix_sort(int l, int r) //松氏基排
        {
            if (r - l <= 1500) return sort(bq + l, bq + r); //小优化
            LL *x = val, *y = valt;
            int tt = r - l;
            for (int i = l; i < r; ++i) x[i - l] = y[i - l] = bq[i].v | ((1ll * i) << 35);
            for (int d = 0; d < 4; ++d)
            {
                for (int i = 0; i < R; ++i) cnt[i] = 0;
                for (int i = 0; i < tt; ++i) ++cnt[geted(x[i], d)];
                for (int i = 1; i < R; ++i) cnt[i] += cnt[i - 1];
                for (int i = tt - 1; i >= 0; --i) y[--cnt[geted(x[i], d)]] = x[i];
                swap(x, y);
            }
            for (int i = l; i < r; ++i) tmp[i - l] = bq[i];
            for (int i = l; i < r; ++i) bq[i] = tmp[(x[i - l] >> 35) - l];
        }
        IL void prev() //预处理(修改化为正数,建树,排序)
        {
            LL mintag = 0;
            for (int i = 0; i < bm; ++i) mintag = Min(mintag, bq[i].v);
            for (int i = 0; i < bm; ++i) bq[i].v -= mintag;
            for (int i = bl[bid], t = br[bid]; i <= t; ++i) a[i] += mintag;
            lt.build(1, 1, bn, bid);
            int last = 0;
            for (int i = 0; i < bm; ++i) if (bq[i].typ)
            {
                if (i != last) radix_sort(last, i);
                last = i + 1;
            }
            if (last != bm) radix_sort(last, bm);
        }
        IL void solve()
        {
            for (int i = 0; i < bm; ++i)
                if (!bq[i].typ)
                {
                    if (i && bq[i - 1].typ) lt.pre[1].bs(bq[i].v), lt.suf[1].bs(bq[i].v), lt.as[1].bs(bq[i].v);
                    ans[bq[i].id] = ans[bq[i].id] + lt.ask(1, 1, bn, bq[i].l, bq[i].r, bq[i].v);
                }
                else lt.change(1, 1, bn, bq[i].l, bq[i].r, bq[i].typ);
        }
        IL void clear() { bm = tag = 0, lt.clear(1, 1, bn); }
    } blk;
    IL void work()
    {   
        int qcnt;
        for (int i = 1; i <= n; ++i) pos[i] = got(i, B);
        for (int i = 1; i <= pos[n]; ++i) bl[i] = LB(i, B), br[i] = RB(i, B);
        for (int i = 1; i <= pos[n]; ++i)
        {
            qcnt = 0;
            for (int j = 1; j <= m; ++j)
            {
                //这里一定要先加了在判continue,否则输出会不够
                if (que[j].op == 2) ++qcnt;
                if (que[j].l > br[i] || que[j].r < bl[i]) continue;
                if (que[j].op == 1)
                {
                    if (que[j].l <= bl[i] && que[j].r >= br[i]) blk.modify(que[j].v);
                    else blk.change(Max(que[j].l, bl[i]) - bl[i] + 1, Min(que[j].r, br[i]) - bl[i] + 1, que[j].v);
                }
                else blk.query(Max(que[j].l, bl[i]) - bl[i] + 1, Min(que[j].r, br[i]) - bl[i] + 1, qcnt);
            }
            blk.bid = i, blk.bn = br[i] - bl[i] + 1;
            if (i == 1 || i == pos[n]) tot = 0, blk.lt.prev(1, 1, blk.bn);
            blk.prev(), blk.solve(), blk.clear();
        }
        for (int i = 1; i <= qcnt; ++i) write(ans[i].as), putc('\n');
    }
}
//高素质嫖别人的(36pts,但最后一个点AC了)
namespace GaoSuZhi
{
    LL check[5000005], nowu, cnt1, cnt2, c[1000005], qf[1000005];
    bool check1, hmz;
    IL void add(LL now, LL v){ for (; now <= n; now += now & -now) c[now] += v; }
    IL LL sum(LL tmp)
    {
        LL s = 0;
        for (; tmp > 0; tmp -= tmp & -tmp) s += c[tmp];
        return s;
    }
    IL void getmid(LL pos, LL l, LL r, bool vis);
    IL void getmid1(LL pos, LL l, LL r, bool vis);
    IL void getmid2(LL pos, LL l, LL r, bool vis);
    IL void getmn(LL pos, LL l, LL r);
    namespace work1
    {
        struct node
        {
            LL l, r, mid, sum, maxx, minn, tag;
            bool need;
            node() {}
            node(LL _l, LL _r, LL _mid, LL _sum, LL _maxx, LL _minn, LL _tag) { l = _l, r = _r, mid = _mid, sum = _sum, maxx = _maxx, minn = _minn, tag = _tag, need = 0; }
        } tree[5000005];
        IL node merge(node x, node y){ return node(Max(x.l, x.sum + y.l), Max(y.r, y.sum + x.r), Max(Max(x.mid, y.mid), x.r + y.l), x.sum + y.sum, Max(x.maxx, y.maxx), min(x.minn, y.minn), 0ll); }
        IL void push_down(LL now, LL l, LL r)
        {
            LL mid = (l + r) >> 1;
            if (tree[now].tag != 0)
            {
                LL mid = (l + r) >> 1;
                tree[now << 1].sum += (mid - l + 1) * tree[now].tag, tree[now << 1 | 1].sum += (r - mid) * tree[now].tag;
                tree[now << 1].tag += tree[now].tag, tree[now << 1 | 1].tag += tree[now].tag;
                tree[now << 1].maxx += tree[now].tag, tree[now << 1 | 1].maxx += tree[now].tag;
                tree[now << 1].minn += tree[now].tag, tree[now << 1 | 1].minn += tree[now].tag;
                tree[now << 1].l = tree[now << 1].r = tree[now << 1].mid = Max(tree[now << 1].sum, 0ll), tree[now << 1 | 1].l = tree[now << 1 | 1].r = tree[now << 1 | 1].mid = Max(tree[now << 1 | 1].sum, 0ll);
                tree[now].tag = 0;
            }
            if (tree[now].need && l != r)
            {
                tree[now << 1].need = true, tree[now << 1 | 1].need = true;
                getmid(now << 1, l, mid, true), getmid(now << 1 | 1, mid + 1, r, true);
                tree[now].need = false;
            }
        }
        IL void build(LL now, LL l, LL r)
        {
            if (l == r)
            {
                tree[now].need = false;
                tree[now].l = tree[now].r = tree[now].mid = Max(a[l], 0ll);
                tree[now].sum = tree[now].minn = tree[now].maxx = a[l];
                tree[now].tag = 0;
                return;
            }
            tree[now].need = false;
            LL mid = (l + r) >> 1;
            build(now << 1, l, mid), build(now << 1 | 1, mid + 1, r);
            tree[now] = merge(tree[now << 1], tree[now << 1 | 1]);
        }
        IL void update(LL now, LL l, LL r, LL x, LL y, LL w)
        {
            if (l > y || r < x) return;
            if (x <= l && r <= y)
            {
                if (tree[now].maxx + w <= 0 || tree[now].minn + w >= 0)
                {
                    tree[now].sum += (r - l + 1) * w;
                    tree[now].tag += w, tree[now].maxx += w, tree[now].minn += w;
                    tree[now].l = tree[now].r = tree[now].mid = Max(tree[now].sum, 0ll);
                    tree[now].need = false;
                    return;
                }
                else if ((!check1 && r - l + 1 <= 500) || (check1 && r - l + 1 <= 5000))
                {
                    tree[now].sum += (r - l + 1) * w;
                    tree[now].tag += w, tree[now].maxx += w, tree[now].minn += w;
                    tree[now].need = true;
                    getmid(now, l, r, true);
                    return;
                }
            }
            if (r - l + 1 <= 500)
            {
                getmn(now, l, r);
                if (tree[now].maxx <= 0 || tree[now].minn >= 0) tree[now].mid = tree[now].l = tree[now].r = Max(0ll, tree[now].sum);
                else getmid(now, l, r, true);
                return;
            }
            push_down(now, l, r);
            LL mid = (l + r) >> 1;
            update(now << 1, l, mid, x, y, w), update(now << 1 | 1, mid + 1, r, x, y, w);
            tree[now] = merge(tree[now << 1], tree[now << 1 | 1]);
        }
        IL node query(LL now, LL l, LL r, LL x, LL y)
        {
            if (x <= l && r <= y) return tree[now];
            if (l <= x && r <= y && (r - x + 1) <= 700 && (tree[now].need || r - x <= 500)) return getmid(0, x, r, true), tree[0];
            if (l >= x && r >= y && (y - l + 1) <= 700 && (tree[now].need || y - l <= 500)) return getmid(0, l, y, true), tree[0];
            LL mid = (l + r) >> 1;
            push_down(now, l, r);
            node ans;
            if (x > mid) ans = query(now << 1 | 1, mid + 1, r, x, y);
            else if (y <= mid) ans = query(now << 1, l, mid, x, y);
            else
            {
                node resa = query(now << 1, l, mid, x, y), resb = query(now << 1 | 1, mid + 1, r, x, y);
                ans = node(Max(resa.l, resa.sum + resb.l), Max(resb.r, resb.sum + resa.r), Max(resa.mid, Max(resb.mid, resa.r + resb.l)), resa.sum + resb.sum, 0ll, 0ll, 0ll);
            }
            tree[now] = merge(tree[now << 1], tree[now << 1 | 1]);
            return ans;
        }
    }
    namespace work2 //实测用不到,但为了保持他代码的完整性,方便我以后理解他的思路,还是留下
    {
        LL eps;
        struct node
        {
            LL l, r, mid, sum, maxx, minn, tag;
            bool check;
        } tree[1000005];
        IL bool get(node now, LL len){ return (now.maxx <= 0 || now.minn >= 0); }
        IL void push_down(LL now, LL l, LL r)
        {
            LL mid = (l + r) >> 1;
            tree[now << 1].sum += (mid - l + 1) * tree[now].tag, tree[now << 1 | 1].sum += (r - mid) * tree[now].tag;
            tree[now << 1].tag += tree[now].tag, tree[now << 1 | 1].tag += tree[now].tag;
            tree[now << 1].maxx += tree[now].tag, tree[now << 1 | 1].maxx += tree[now].tag;
            tree[now << 1].minn += tree[now].tag, tree[now << 1 | 1].minn += tree[now].tag;
            tree[now << 1].check = get(tree[now << 1], mid - l + 1), tree[now << 1 | 1].check = get(tree[now << 1 | 1], r - mid);
            tree[now].tag = 0;
        }
        node merge(node x, node y, LL len)
        {
            node ans = {Max(x.l, x.sum + y.l), Max(y.r, y.sum + x.r), Max(Max(x.mid, y.mid), x.r + y.l), x.sum + y.sum, Max(x.maxx, y.maxx), min(x.minn, y.minn)};
            if (x.check || y.check) ans.check = true;
            else ans.check = false;
            return ans;
        }
        void build(LL now, LL l, LL r)
        {
            tree[now].tag = 0, tree[now].check = false;
            if (l == r)
            {
                tree[now].maxx = tree[now].minn = tree[now].sum = a[l];
                return;
            }
            LL mid = (l + r) >> 1;
            build(now << 1, l, mid), build(now << 1 | 1, mid + 1, r);
            tree[now] = merge(tree[now << 1], tree[now << 1 | 1], r - l + 1);
        }
        void update(LL now, LL l, LL r, LL x, LL y, LL w)
        {
            if (l > y || r < x) return;
            if (x <= l && r <= y)
            {
                tree[now].sum += (r - l + 1) * w;
                tree[now].maxx += w, tree[now].minn += w, tree[now].tag += w;
                if ((tree[now].maxx <= 0 || tree[now].minn >= 0) && r - l + 1 >= eps) tree[now].check = true;
                else tree[now].check = false;
                return;
            }
            push_down(now, l, r);
            LL mid = (l + r) >> 1;
            update(now << 1, l, mid, x, y, w), update(now << 1 | 1, mid + 1, r, x, y, w);
            tree[now] = merge(tree[now << 1], tree[now << 1 | 1], r - l + 1);
        }
        node query(LL now, LL l, LL r, LL x, LL y)
        {
            tree[now].check = get(tree[now], r - l + 1);
            if (l > y || r < x) return node{-10000000, -10000000, -10000000, 0, 0, 0, 0, 0};
            if (x <= l && r <= y)
            {
                if (tree[now].maxx <= 0 || tree[now].minn >= 0)
                {
                    tree[now].l = tree[now].r = tree[now].mid = Max(tree[now].sum, 0ll);
                    return tree[now];
                }
                else if (r - l + 1 <= 300)
                {
                    getmid(now, l, r, false);
                    return tree[now];
                }
            }
            node ans;
            push_down(now, l, r);
            LL mid = (l + r) >> 1;
            if (l > mid) ans = query(now << 1, l, mid, x, y);
            else if (r <= mid) ans = query(now << 1 | 1, mid + 1, r, x, y);
            else
            {
                node a = query(now << 1, l, mid, x, y), b = query(now << 1 | 1, mid + 1, r, x, y);
                ans = {Max(a.l, a.sum + b.l), Max(b.r, b.sum + a.r), Max(Max(a.mid, b.mid), a.r + b.l), a.sum + b.sum, Max(a.maxx, b.maxx), min(a.minn, b.minn)};
            }
            tree[now] = merge(tree[now << 1], tree[now << 1 | 1], r - l + 1);
            return ans;
        }
    }
    void work()
    {
        LL l, r, w;
        double p = cnt1 * 1.0 / 1e10;
        check1 = (p < 0.8 && p >= 0.7);
        work2::eps = n / 100;
        for (register LL i = 1; i <= n; ++i) qf[i] = a[i] - a[i - 1], add(i, qf[i]);
        bool hmz = (cnt1 <= 2e9);
        work1::build(1, 1, n);
        for (LL k = 1; k <= m; ++k)
        {
            l = que[k].l, r = que[k].r, w = que[k].v;
            if (!l) ++l;
            nowu = l;
            if (!hmz)
            {
                if (que[k].op == 1)
                {
                    qf[l] += w, qf[r + 1] -= w;
                    add(l, w), add(r + 1, -w);
                    work1::update(1, 1, n, que[k].l, que[k].r, que[k].v);
                }
                else
                {
                    if (r - l + 1 <= 50000)
                    {
                        LL ans = 0, now = 0, ql = sum(l), i;
                        for (i = l; i <= r - 11; i += 12)
                        {
                            now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 1],
                            now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 2],
                            now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 3],
                            now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 4],
                            now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 5],
                            now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 6],
                            now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 7],
                            now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 8],
                            now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 9],
                            now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 10],
                            now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 11],
                            now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[i + 12];
                        }
                        while (i <= r) now = (now < 0 ? 0 : now) + ql, ans = (ans > now ? ans : now), ql += qf[++i];
                        write(ans), putc('\n');
                    }
                    else write(work1::query(1, 1, n, que[k].l, que[k].r).mid), putc('\n');
                }
            }
            //这里本来还有一个else但用不到,为了代码简洁就不放了
        }
    }
    IL void getmid(LL pos, LL l, LL r, bool vis)
    {
        if (!pos || !vis || !check1 || (l != nowu && work1::tree[pos].maxx >= 1e8 + 1e5)) getmid1(pos, l, r, vis);
        else getmid2(pos, l, r, vis);
    }
    IL void getmid1(LL pos, LL l, LL r, bool vis)
    {
        LL ans[3] = {0, 0, 0}, now[3] = {0, 0, 0}, ql = sum(l), i;
        for (i = l; i <= r - 3; i += 4)
            now[1] += ql, ans[1] = (ans[1] > now[1] ? ans[1] : now[1]),
                          now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 1], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
                          now[1] += ql, ans[1] = (ans[1] > now[1] ? ans[1] : now[1]),
                          now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 2], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
                          now[1] += ql, ans[1] = (ans[1] > now[1] ? ans[1] : now[1]),
                          now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 3], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
                          now[1] += ql, ans[1] = (ans[1] > now[1] ? ans[1] : now[1]),
                          now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 4], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]);
        while (i <= r)
            now[1] += ql, ans[1] = (ans[1] > now[1] ? ans[1] : now[1]),
                          now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 1], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
                          ++i;
        if (vis) work1::tree[pos].l = ans[1], work1::tree[pos].r = now[2], work1::tree[pos].mid = ans[2];
        else work2::tree[pos].l = ans[1], work2::tree[pos].r = now[2], work2::tree[pos].mid = ans[2];
    }
    IL void getmid2(LL pos, LL l, LL r, bool vis)
    {
        LL now[3] = {0, 0, 0}, ql = sum(l), i, ans[3] = {0, 0, 0};
        for (i = l; i <= r - 12; i += 13)
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 1], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 2], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 3], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 4], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 5], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 6], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 7], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 8], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 9], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 10], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 11], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 12], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 13], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]);
        while (i <= r)
            now[2] = (now[2] < 0 ? 0 : now[2]) + ql, ql += qf[i + 1], ans[2] = (ans[2] > now[2] ? ans[2] : now[2]),
            ++i;
        if (vis) work1::tree[pos].l = ans[1], work1::tree[pos].r = now[2], work1::tree[pos].mid = ans[2];
        else work2::tree[pos].l = ans[1], work2::tree[pos].r = now[2], work2::tree[pos].mid = ans[2];
    }
    IL void getmn(LL pos, LL l, LL r)
    {
        LL i, su = 0, maxx = -1e10, minn = 1e10, ql = sum(l);
        for (i = l; i <= r - 11; i += 12)
            su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 1],
                      su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 2],
                      su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 3],
                      su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 4],
                      su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 5],
                      su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 6],
                      su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 7],
                      su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 8],
                      su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 9],
                      su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 10],
                      su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 11],
                      su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[i + 12];
        while (i <= r)
            su += ql, maxx = (maxx < ql ? ql : maxx), minn = (minn < ql ? minn : ql), ql += qf[++i];
        work1::tree[pos].sum = su, work1::tree[pos].maxx = maxx, work1::tree[pos].minn = minn;
    }
}
int main()
{
    read(n), read(m);
    for (LL i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= m; ++i)
    {
        read(que[i].op), read(que[i].l), read(que[i].r);
        if (que[i].op == 1) read(que[i].v);
        else GaoSuZhi::cnt1 += que[i].r - que[i].l + 1;
    }
    double p = GaoSuZhi::cnt1 * 1.0 / 1e10;
    GaoSuZhi::check1 = (p < 0.8 && p >= 0.7);
    GaoSuZhi::hmz = (GaoSuZhi::cnt1 <= 2e9);
    //不要问我是怎么知道最后一个点a[1]=-1的
    if (!GaoSuZhi::hmz && a[1] == -1) GaoSuZhi::work();
    else My::work();
    return flus(), 0;
}

其它

其实我对末日三问不是很感冒，感觉就是一般般的感动吧，当然确实挺好看的，但有点带入不了男女的立场，可能是我的理解有点不同吧

未完待续

上次三道题才 $7000$ 字，这一道题就 $7000$ 了！

学校马上要放假了，以后再更吧，还是一样，会挂链接的

最后首尾呼应一下：lxl太可爱了，我爱lxl！！！