我写这篇题解主要作用是帮助那些需要卡常的，如果需要学习主要做法的话可以参考 Sol1 大佬的这篇文章。

在这道题上我的代码拿到了最优解，总时间 9.51s（未开 O2），单点最慢 626ms，唯一一个跑进 10s 内的。 由于一些神秘的原因，开了 O2 反而变慢了，跑了个 9.68s。

1. 带权分块：

针对 80pts 被卡最后5个 Hack 数据的，能优化很多时间。 首先带权分块和普通分块的主要区别就是块长，普通分块固定块长对于随机数据跑得很快，但是对于 Hack 的构造数据会被卡飞，原因就是它的时间复杂度核心并不是普通的 $块数 \times m$，而是 $\sum 散块的修改次数 \times 块长$，如果某些位置被大量散块修改覆盖，固定块长会让这些热点块代价很高。带权分块就是先根据操作分布估计每个候选块 [L,R] 的代价，然后用 DP 选块边界。 然后就是代价模型，一般用的是 $散块修改次数 \times 块长+整块查询次数 \times KK$，其中 $KK$ 是一个等块查询的等效常数，散块修改贵，因为会触发块内线段树 pull，重建凸包；整块查询相对便宜，因为可以离线排序后双指针扫。 实现时不需要枚举所有 L,R，否则 DP 本身太慢。一般只允许右端点是 D 的倍数，并限制最大块长 AX。针对本道题用的参数：D=100, AX=5000, KK=15。

感谢 王熙文 在这篇中提供的参数，让我减少了很多调参的时间。

2. 块内凸包不要用 vector：

这个是较为一般的卡常方式了，但确实能节省很多时间，那我就来解释一下原因吧。 块内线段树的每个节点都要维护三类凸包：前缀最优值的凸包、后缀最优值的凸包、最大子段和的凸包。如果这些凸包使用动态容器保存，那么每次重建节点时可能发生清空、扩容、重新分配、析构、拷贝等操作。 显然这道题的数据中会出现大量这种操作，动态内存分配的成本会非常高，而且会破坏缓存局部性。 更快的方式是使用预先分配好的连续内存池。每个节点只记录自己在内存池中的起始位置和凸包长度。这样所有凸包点都放在连续数组里，避免堆分配，访问也更集中。

这种是针对运算较底层的优化了，一般只用使用就行了，不需要知道原理。

3.整块查询：

整块查询时，只需要查询块根节点上的凸包。如果每次查询都在凸包上二分，会多一个对数，而且常数不小。 更好的做法是逐块离线处理。处理某个块时，遇到整块查询先不立刻回答，而是记录当时这个块的整体加标记和询问编号。等到必须处理这些查询时，把它们按整体加标记排序。 排序后，凸包上的最优点会单调移动，可以用指针扫，而不是每次二分。也就是说，一批整块查询可以接近线性处理。

4. 排序优化：

用整数基数排序，原因不用多说。 但小批量事件用插入排序，如果某次积攒的整块查询事件很少，基数排序反而不划算。因为基数排序每次都要清空桶、扫描多轮，即使只有几十个元素，也要付固定成本。 小数组用插入排序更快。尤其这题里，事件的整体加标记经常局部接近有序，插入排序在这种情况下常数很低。

如果有序就跳过排序：

在积攒整块查询事件时，可以顺便判断当前整体加标记是否保持非降序。如果一直有序，那么处理时不需要排序，直接用指针扫凸包即可。 这个判断成本极低，只需要比较新加入的标记和上一个标记。对于某些数据，尤其是整体修改方向比较单一的数据，可以省掉大量排序时间。

这里也是针对构造数据的，随机数据基本没啥用。

5. 最大字段和优化：

一次区间查询最终要把很多块或很多线段树节点的结果合并起来。每个结果包含四个值：区间和、最大前缀和、最大后缀和、最大子段和。 如果每次合并都返回一个新的结构体，会产生大量临时对象。这个结构体一般有四个 64 位整数，大小不算小。频繁传值和返回会增加寄存器压力，也可能产生栈上的读写。 更快的方式是把右边结果直接合并进左边结果，也就是原地更新。这样可以减少临时对象和结构体拷贝。

简单来说就是如果你相信评测姬的实力就不用，实际 CCF 的评测姬跑得飞快，所以可以不用，但洛谷的评测姬的话……

6. 函数返回的优化：

块根查询和散块查询都会频繁返回四元信息。如果通过函数返回值返回，编译器虽然可能优化，但在递归和复杂控制流下不一定完全消掉。 解决方法是把结果对象传进去，让函数直接写入。这样减少返回大对象的开销，也降低寄存器分配压力。

用处不大，但很稳定，至少能保证对所有数据都有优化。

7. 快读快写：

优秀的快读快写可以极大的优化你的常数，感谢 Hootime 提供的代码，我也在这里放出来吧： :::info[Code]

#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){
    x = 0; int w = 1;
    char ch = gc();
    while(ch < '0' || ch > '9'){
        if(ch == '-') w = -w;
        ch = gc();
    }
    while(ch >= '0' && ch <= '9')
        x = (x<<3)+(x<<1)+(ch^48), ch = gc();
    x *= w;
}
template<typename T, typename... Args>
inline void read(T& x, Args&... y){
    return read(x), read(y...);
}

在本题中扔掉处理负数片段以获得更大优化。 :::

8. 操作数组扫描的优化：

一定要顺序扫描，不要盲目打包！！！

直觉上，把操作类型、左右端点、编号压到一个整数里，似乎能减少内存访问。但实际经常变慢。 每次处理操作时都需要解码，包括移位、掩码和类型判断。而且修改值仍然需要额外访问。相比之下，分开的数组虽然看起来多，但每一轮都是从头到尾顺序扫描，CPU 的预取效果很好。 另一种看似合理的优化是：提前把每个操作分发到它影响的块里，这样每个块不用扫所有操作。 但如果用链表或分散存储，会破坏顺序访问。CPU 很难预取链式跳转的数据，cache miss 会增加。而且一个长区间操作会被挂到很多块上，预处理数据量也会膨胀。 当前做法虽然每个块都顺序扫所有操作，但访问模式非常稳定，缓存友好。除非预分发做成非常紧凑的连续数组，否则容易变慢。

9. 凸包合并循环的优化：

散块修改最重的地方是重建线段树节点的信息。重建时要合并前缀凸包、后缀凸包、最大子段和凸包，还要做一次类似闵可夫斯基和的合并。 这些循环里会反复计算“某个点在当前整体加标记下的实际值”。如果每次都通过一个辅助函数计算，或者反复计算相邻两个点的实际值差，会浪费很多乘法和数组读取。 更好的方式是直接使用相邻点的差值：横坐标差乘标记，加上纵坐标差。这样能减少函数调用和重复乘法。

10. 关于 int128：

一般来说，人们会对超出 long long 范围的数值使用 __int128 存储，但你要知道，有些题目只是输入需要，并不是运算中也需要。 如果能证明数值不会溢出 64 位，就应该用 64 位整数。由于这题保证任意时刻单个元素绝对值不超过一定范围，块长又有限，很多地方的乘积实际不会超过 64 位范围。 但是这个优化有风险。如果证明不严谨，可能出现隐藏溢出导致错误答案。比较稳的做法是：只在最可能溢出的少数斜率比较处保留 128 位，其它地方用 64 位。 因为 64 位比 128 位快。

11.查询时要下传标记：

散块查询只读信息，不修改结构。查询递归时，可以把沿途经过的整体加标记累加成一个参数传下去。到达完整覆盖节点时，用这个累积标记去查询凸包。 这样查询不会改变线段树状态，也不会触发标记下传和重建。只有散块修改才需要下传标记，因为修改后要重新合并父节点信息。

12.合理安排批处理时机：

整块查询可以延迟批处理，但不能无限延迟。因为一旦出现散块修改，块内线段树结构会改变，之前积攒的查询必须在修改前处理掉。 这个貌似 O2 会帮你做（之前貌似看到过，但有些忘记了，如果写错了记得叫我），但自己做了肯定要好一点。 流程大概是这样： 遇到整块修改，只更新块的整体加标记。 遇到整块查询，记录当前整体加标记和询问编号。 遇到散块查询，直接在线段树上查询。 遇到散块修改，先处理之前积攒的整块查询，再执行散块修改。 如果过早处理整块查询，排序批次变多，常数变大。如果过晚处理，会因为线段树状态改变而答案错误。

13.一些关于负优化的：

1. 首先是关于三目运算符，不要以为它和位运算长得像就以为它要快一点。 现代 CPU 对稳定分支预测很强。如果一个条件的分布比较稳定，普通条件语句往往已经很好。 三目表达式如果写得复杂，可能导致重复计算。特别是在凸包合并里，如果一个三目表达式中重复计算多个点的实际值，反而会变慢。
2. 不要把点结构强行压缩对齐，凸包上的每个点包含一个长度和一个对应的最优值。长度是较小整数，值是 64 位整数。按正常结构体存储时，中间可能有填充字节，看起来浪费空间。 但如果强行压缩结构体，64 位整数可能变成非对齐访问。非对齐访问虽然在某些 CPU 上可以运行，但通常更慢，而且可能跨缓存行。 这题凸包点的 64 位值是热路径中高频读取的数据，所以应保持自然对齐，不要强行压缩！
3. 不要给所有大数组强行缓存行对齐。缓存行对齐对某些小而热的数据有用，比如排序桶。但如果给大量大数组都强行对齐，可能扩大内存布局，增加页表和缓存压力。 大数组的访问模式更重要。顺序访问的大数组，即使没有手动对齐，也能被 CPU 预取很好地处理。乱加对齐不一定有收益，甚至可能变慢。

4. O2 可能对你的代码负优化！！！非常重要！！！

14. 调参：

不说了好吧，一杯茶，一包烟，一个块长调一天。 嗯……还是写一下吧： :::info[调块长的技巧] 分块调参的方法不是取根号，而是先写出这份分块的真实代价模型，然后按模型求一个理论块长，再围绕这个值实测微调。不同分块的最优块长差别很大，$\sqrt n$ 只是最常见的一种特例。 设块长为 $B$，块数大约是 $n/B$。 很多分块操作的代价可以拆成两类： 一种是散块代价，也就是区间左右两端不完整块的处理。它通常和 $B$ 成正比。 另一种是整块代价，也就是中间完整块的处理。它通常和 $n/B$ 成正比。 所以最常见模型是：$单次操作代价 \approx C_1 \times B + C_2 \times n / B$。 如果两边常数差不多，最优块长就是：$B=\sqrt n$; 但实际常数经常不一样，所以更准确是：$B = \sqrt {\frac{C_2 \times n} {C_1}}$。 也就是说，如果散块处理特别贵，就应该减小块长；如果整块处理特别贵，就应该增大块长。 有些分块里，散块只是暴力扫元素，而整块查询只读一个预处理值。这时散块常数大，整块常数小，块长应该偏小。 如果整块处理要做二分、排序、合并结构，整块常数大，块长应该偏大，减少块数。 经验上：

• 散块贵：块长取小一点；
• 整块贵：块长取大一点；
• 重构贵：块长取小一点；
• 每块初始化贵：块长取大一点；
• 每次都扫所有块：块长取大一点；
• 每次都暴力扫散块：块长取小一点；

带修改的分块经常会出现“散块修改后重构整个块”的情况。 如果一次散块修改要重构一个块，重构代价是 $O(B \log B)$ 或 $O(B)$，那么散块修改会很贵。此时块长不能太大。 模型可能变成： $修改代价 \approx C_1 \times B 或 C1 \times B \log B$； $查询代价 \approx \frac{C_2 \times n}{B}$。 如果修改次数和查询次数差不多，块长仍然接近根号，但会比普通根号小一些，因为重构常数通常很高。 如果修改远多于查询，块长应继续减小。 如果查询远多于修改，块长可以增大。

有些分块维护块内所有答案，重构一个块需要 $O(B^2)$。 这时模型大概是：$总代价 \approx 修改次数 \times B^2 + \frac{查询次数 \times n}{B}$； 平衡之后，块长不是根号，而接近：$B \approx cube\_root(\frac{查询次数 \times n}{修改次数})$。 所以凡是块内维护二维信息、所有子区间信息、块内 DP 表之类的分块，块长一般不能取太大。 有些分块里整块不是 $O(1)$，而是：

• $O(\log B)$；
• $O(\log 值域)$；
• $O(二分次数)$；
• $O(小数据结构查询)$；

那么中间完整块代价是：$\frac{n}{B} \times \log B$； 模型变成：$C_1\times B + \frac{C_2\times n}{B}\times \log B$。 这时最优块长一般会比普通根号略大。因为块长增大虽然让散块更贵，但能减少完整块数量，而完整块每个还有对数常数。

有些分块中，散块不是纯暴力扫，而是在线段树、平衡结构、凸包上查询。散块代价可能是：

• $\log B$
• $\log^2 B$
• $B 的一小部分$

如果散块已经不那么贵，那么可以适当增大块长来减少块数。 现在这类题就是典型例子：散块查询不算特别重，真正重的是散块修改造成的凸包重构。因此调块长时不能只看查询，要重点看修改分布。

普通莫队常见块长是 $\sqrt n$，但更准确的模型是：

• $左端点移动代价 \approx 查询数 \times B$
• $右端点移动代价 \approx \frac{n^2}{B}$

所以最优块长大约是：$B \approx \frac{n}{\sqrt{查询数}}$。 如果查询数和 $n$ 同阶，就是 $\sqrt n$。 如果查询数远大于 $n$，块长应该更小； 如果查询数远小于 $n$，块长应该更大。

带修改莫队有三个维度：左端点、右端点、时间。块长一般和 $n^{\frac{2}{3}}$ 有关。 粗略经验是： $位置块长 \approx n^{\frac{2}{3}}$； $时间块长 \approx n^{\frac{2}{3}}$。 但具体还要看修改代价和增删代价。如果修改应用/撤销比普通移动贵，时间块应该调大，减少时间维移动次数。 这类题块长尤其要实测，理论值只能作为起点。

位置分块的块长通常围绕 $\sqrt n$ 调。 值域分块要看值域大小 $V$，而不是数组长度 $n$。如果按值域分块，块长应该根据 $V$、操作数量、单次桶处理代价来定。 例如值域统计中： $散值处理 \approx B$； $整桶处理 \approx \frac{V}{B}$。 那么块长接近：$\sqrt V$； 如果值域经过离散化，应该用离散化后的大小，而不是原始值域。

如果分块里使用 bitset 或手写位集，块长最好和机器字长相关。 因为 bitset 的基本处理单位通常是 64 位。块长取 64 的倍数、128 的倍数、256 的倍数，常数会更稳定。 原因是按 64 位对齐后，循环次数、内存访问和尾部处理都更规整。

固定块长假设操作分布比较均匀。但 hack 数据往往会集中攻击某些位置。 如果某一段被大量散块修改，固定块长会很吃亏。 带权分块的做法是让热点区域块短一点，让冷门区域块长一点。这样能降低热点块的重构代价，同时不让总块数太多。 适用场景：操作分布不均匀、最后几个点是 hack、散块修改代价很高、块长对时间非常敏感……

带权分块的参数怎么调？

带权分块一般有三个参数。 第一个是候选断点间隔。间隔越小，DP 分块越精细，但预处理更慢。一般从 $100$ 左右试。 第二个是最大块长。最大块长太大，单块数据结构会变重，散块修改变慢；太小，块数太多，每块扫操作和整块查询变慢。可以从 $3000$ 到 $7000$ 测。 第三个是整块查询权重。这个值越大，DP 越倾向于减少整块查询代价；越小，越倾向于减少散块修改代价。一般从 $10$ 到 $25$ 试。

一些神秘知识：块长太大时，单块内部数据结构可能放不进 L2 cache，甚至频繁打到 L3。虽然理论操作次数少了，但 cache miss 会变多。 块长太小时，块数增加，每次操作扫描块或处理块元信息的次数变多。

最后，一定要多侧块长，不要光测测数值，测得越多对你调参更友好，希望大家不要在被困在调块长的深渊里了。 :::

最后放一下我的完整代码吧： :::info[CODE]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define BS (1<<20)
#define IL inline __attribute__((always_inline))
const int N=100000+5,D=100,AX=5000,K=AX+5,M=AX*4+20,Q=85000,PN=N*20,KK=15;
const ll OF=5000000000LL,INF=4000000000000000000LL;
char ib[BS],*p1=ib,*p2=ib,ob[BS];
int oop;
#define gc() (p1==p2&&(p2=(p1=ib)+fread(ib,1,BS,stdin),p1==p2)?EOF:*p1++)
IL int ru(){
    int x=0;char c=gc();
    while(c<'0'||c>'9')c=gc();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=gc();
    return x;
}
IL ll rs(){
    ll x=0;int w=1;char c=gc();
    while(c!='-'&&(c<'0'||c>'9'))c=gc();
    if(c=='-')w=-1,c=gc();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=gc();
    return x*w;
}
IL void pc(char c){
    if(oop==BS)fwrite(ob,1,oop,stdout),oop=0;
    ob[oop++]=c;
}
IL void wt(ll x){
    char s[24];int n=0;
    if(!x){pc('0');return;}
    if(x<0)pc('-'),x=-x;
    while(x)s[n++]=x%10+48,x/=10;
    while(n--)pc(s[n]);
}
struct P{int x;ll y;};
struct V{ll s,l,r,a;};
IL ll gv(P p,ll t){return p.y+(ll)p.x*t;}
IL bool bad(P a,P b,P c){
    return (b.y-a.y)*(ll)(c.x-b.x)<=(c.y-b.y)*(ll)(b.x-a.x);
}
IL void hp(P *h,int &n,P p){
    while(n&&h[n-1].x==p.x){
        if(h[n-1].y>=p.y)return;
        n--;
    }
    while(n>=2&&bad(h[n-2],h[n-1],p))n--;
    h[n++]=p;
}
IL ll ah(P *h,int n,ll t){
    int l=0,r=n-1;
    while(l<r){
        int m=(l+r)>>1;
        ll x=h[m].y+(ll)h[m].x*t,y=h[m+1].y+(ll)h[m+1].x*t;
        if(x<=y)l=m+1;
        else r=m;
    }
    return h[l].y+(ll)h[l].x*t;
}
IL ll askp(P *h,int n,ll t,int &p){
    while(p+1<n&&h[p].y+(ll)h[p].x*t<=h[p+1].y+(ll)h[p+1].x*t)p++;
    return h[p].y+(ll)h[p].x*t;
}
IL void mgto(V &a,const V &b){
    ll s=a.s+b.s;
    ll l=a.l,x=a.s+b.l;
    if(x>l)l=x;
    ll r=b.r;
    x=b.s+a.r;
    if(x>r)r=x;
    ll z=a.a>b.a?a.a:b.a;
    x=a.r+b.l;
    if(x>z)z=x;
    a.s=s;a.l=l;a.r=r;a.a=z;
}
struct B{
    int n,tp,ln[M],cl[M],cr[M],ca[M],of[M];
    ll d[K],sm[M],tg[M];
    P lp[Q],rp[Q],apol[Q],cy[K*2];
    IL P* gl(int o){return lp+of[o];}
    IL P* gr(int o){return rp+of[o];}
    IL P* ga(int o){return apol+of[o];}
    IL void pd(int o){
        ll z=tg[o];
        if(!z)return;
        tg[o<<1]+=z;
        tg[o<<1|1]+=z;
        tg[o]=0;
    }
    void mk(P *a,int na,ll ta,P *b,int nb,ll tb,P *c,int &nc){
        nc=0;
        if(!na||!nb)return;
        int i=0,j=0,o;
        P p;
        p.x=a[0].x+b[0].x;
        p.y=a[0].y+(ll)a[0].x*ta+b[0].y+(ll)b[0].x*tb;
        hp(c,nc,p);
        while(i+1<na||j+1<nb){
            if(j+1==nb)o=1;
            else if(i+1==na)o=2;
            else{
                int ax=a[i+1].x-a[i].x,bx=b[j+1].x-b[j].x;
                ll ay=a[i+1].y-a[i].y+(ll)ax*ta;
                ll by=b[j+1].y-b[j].y+(ll)bx*tb;
                o=(ay*bx>=by*ax)?1:2;
            }
            if(o==1){
                int dx=a[i+1].x-a[i].x;
                p.x+=dx;
                p.y+=a[i+1].y-a[i].y+(ll)dx*ta;
                i++;
            }else{
                int dx=b[j+1].x-b[j].x;
                p.x+=dx;
                p.y+=b[j+1].y-b[j].y+(ll)dx*tb;
                j++;
            }
            hp(c,nc,p);
        }
    }
    void m3(P *a,int na,ll ta,P *b,int nb,ll tb,P *c,int nc,P *d,int &nd){
        nd=0;
        int i=0,j=0,k=0;
        while(i<na||j<nb||k<nc){
            int x=INT_MAX;
            if(i<na&&a[i].x<x)x=a[i].x;
            if(j<nb&&b[j].x<x)x=b[j].x;
            if(k<nc&&c[k].x<x)x=c[k].x;
            ll y=-(1LL<<60),v;
            while(i<na&&a[i].x==x){
                v=a[i].y+(ll)a[i].x*ta;
                if(v>y)y=v;
                i++;
            }
            while(j<nb&&b[j].x==x){
                v=b[j].y+(ll)b[j].x*tb;
                if(v>y)y=v;
                j++;
            }
            while(k<nc&&c[k].x==x){
                if(c[k].y>y)y=c[k].y;
                k++;
            }
            hp(d,nd,(P){x,y});
        }
    }
    void init(int m,ll *s){
        n=m;tp=0;
        for(int i=1;i<=n;i++)d[i]=s[i];
        bd(1,1,n);
    }
    void bd(int o,int l,int r){
        of[o]=tp;
        tp+=r-l+2;
        tg[o]=0;
        ln[o]=r-l+1;
        if(l==r){
            sm[o]=d[l];
            cl[o]=cr[o]=ca[o]=0;
            P p;
            p.x=0;p.y=0;
            hp(gl(o),cl[o],p);
            hp(gr(o),cr[o],p);
            hp(ga(o),ca[o],p);
            p.x=1;p.y=d[l];
            hp(gl(o),cl[o],p);
            hp(gr(o),cr[o],p);
            hp(ga(o),ca[o],p);
            return;
        }
        int m=(l+r)>>1;
        bd(o<<1,l,m);
        bd(o<<1|1,m+1,r);
        pu(o);
    }
    void pu(int o){
        int a=o<<1,b=o<<1|1;
        ll ta=tg[a],tb=tg[b],ls=sm[a]+ta*ln[a],rs=sm[b]+tb*ln[b];
        int nl=ln[a],nr=ln[b];
        P *ol=gl(o),*orx=gr(o),*oa=ga(o);
        P *al=gl(a),*ar=gr(a),*aa=ga(a);
        P *bl=gl(b),*br=gr(b),*ba=ga(b);
        ln[o]=nl+nr;
        sm[o]=ls+rs;
        tg[o]=0;
        cl[o]=0;
        for(int i=0,ed=cl[a];i<ed;i++)hp(ol,cl[o],(P){al[i].x,al[i].y+(ll)al[i].x*ta});
        for(int i=0,ed=cl[b];i<ed;i++)hp(ol,cl[o],(P){bl[i].x+nl,bl[i].y+(ll)bl[i].x*tb+ls});
        cr[o]=0;
        for(int i=0,ed=cr[b];i<ed;i++)hp(orx,cr[o],(P){br[i].x,br[i].y+(ll)br[i].x*tb});
        for(int i=0,ed=cr[a];i<ed;i++)hp(orx,cr[o],(P){ar[i].x+nr,ar[i].y+(ll)ar[i].x*ta+rs});
        int cn;
        mk(ar,cr[a],ta,bl,cl[b],tb,cy,cn);
        m3(aa,ca[a],ta,ba,ca[b],tb,cy,cn,oa,ca[o]);
    }
    void add(int o,int l,int r,int ql,int qr,ll k){
        if(ql<=l&&r<=qr){tg[o]+=k;return;}
        pd(o);
        int m=(l+r)>>1;
        if(ql<=m)add(o<<1,l,m,ql,qr,k);
        if(qr>m)add(o<<1|1,m+1,r,ql,qr,k);
        pu(o);
    }
    IL void add(int l,int r,ll k){add(1,1,n,l,r,k);}
    IL void all(ll k){tg[1]+=k;}
    IL ll gt(){return tg[1];}
    IL void va(int o,ll t,V &v){
        t+=tg[o];
        v.s=sm[o]+t*ln[o];
        v.l=ah(gl(o),cl[o],t);
        v.r=ah(gr(o),cr[o],t);
        v.a=ah(ga(o),ca[o],t);
    }
    IL void rt(ll t,int &p,int &q,int &r,V &v){
        v.s=sm[1]+t*ln[1];
        v.l=askp(gl(1),cl[1],t,p);
        v.r=askp(gr(1),cr[1],t,q);
        v.a=askp(ga(1),ca[1],t,r);
    }
    void qry(int o,int l,int r,int ql,int qr,ll t,V &v){
        if(ql<=l&&r<=qr){
            V z;va(o,t,z);mgto(v,z);return;
        }
        t+=tg[o];
        int m=(l+r)>>1;
        if(ql<=m)qry(o<<1,l,m,ql,qr,t,v);
        if(qr>m)qry(o<<1|1,m+1,r,ql,qr,t,v);
    }
    IL void qry(int l,int r,V &v){v.s=v.l=v.r=v.a=0;qry(1,1,n,l,r,0,v);}
}ds;
int ls[PN],rsn[PN],su[PN],rtp[N],pcn;
int up(int p,int l,int r,int x){
    int q=++pcn;
    ls[q]=ls[p];rsn[q]=rsn[p];su[q]=su[p]+1;
    if(l!=r){
        int m=(l+r)>>1;
        if(x<=m)ls[q]=up(ls[p],l,m,x);
        else rsn[q]=up(rsn[p],m+1,r,x);
    }
    return q;
}
int qu(int p,int l,int r,int ql){
    if(!p||r<ql)return 0;
    if(ql<=l)return su[p];
    int m=(l+r)>>1;
    return qu(ls[p],l,m,ql)+qu(rsn[p],m+1,r,ql);
}
IL ull ky(ll x){return (ull)(x+OF);}
ll et[N],bt[N];
int ei[N],bi[N],ct[256];
void sr(int n){
    if(n<=1)return;
    if(n<80){
        for(int i=1;i<n;i++){
            ll t=et[i];int id=ei[i],j=i-1;
            while(j>=0&&et[j]>t){et[j+1]=et[j];ei[j+1]=ei[j];j--;}
            et[j+1]=t;ei[j+1]=id;
        }
        return;
    }
    ll *pa=et,*pb=bt,*pt;
    int *ia=ei,*ib=bi,*it;
    for(int sh=0;sh<40;sh+=8){
        memset(ct,0,1024);
        for(int i=0;i<n;i++)ct[(ky(pa[i])>>sh)&255]++;
        int p=0;
        for(int i=0;i<256;i++){int v=ct[i];ct[i]=p;p+=v;}
        for(int i=0;i<n;i++){
            int v=(ky(pa[i])>>sh)&255,p=ct[v]++;
            pb[p]=pa[i];ib[p]=ia[i];
        }
        pt=pa;pa=pb;pb=pt;
        it=ia;ia=ib;ib=it;
    }
    if(pa!=et){memcpy(et,pa,n<<3);memcpy(ei,ia,n<<2);}
}
ll a[N],ta[K],dp[2005];
int tp[N],lq[N],rq[N],idq[N];
ll xq[N];
V an[N];
int hd[N],nq[N],qr[N],ul[N],ur[N],sl[N],srp[N],en[2005],fr[2005],bl[2005],br[2005];
int main(){
    int n=ru(),m=ru();
    for(int i=1;i<=n;i++)a[i]=rs();
    int qc=0;
    for(int i=1;i<=m;i++){
        tp[i]=ru();lq[i]=ru();rq[i]=ru();
        if(tp[i]==1){xq[i]=rs();ul[lq[i]]++;ur[rq[i]]++;}
        else{idq[i]=++qc;qr[qc]=rq[i];nq[qc]=hd[lq[i]];hd[lq[i]]=qc;}
    }
    for(int i=1;i<=n;i++){
        sl[i]=sl[i-1]+ul[i];
        srp[i]=srp[i-1]+ur[i];
        rtp[i]=rtp[i-1];
        for(int j=hd[i];j;j=nq[j])rtp[i]=up(rtp[i],1,n,qr[j]);
    }
    int ec=0;en[0]=0;
    for(int i=D;i<n;i+=D)en[++ec]=i;
    if(en[ec]!=n)en[++ec]=n;
    dp[0]=0;fr[0]=0;
    for(int i=1;i<=ec;i++){
        dp[i]=INF;fr[i]=i-1;
        for(int j=i-1;j>=0&&en[i]-en[j]<=AX;j--){
            int L=en[j]+1,R=en[i],le=R-L+1;
            ll c=(ll)(sl[R]-sl[L])+(ll)(srp[R-1]-srp[L-1]);
            ll q=qu(rtp[L],1,n,R);
            ll v=dp[j]+c*le+q*KK;
            if(v<dp[i])dp[i]=v,fr[i]=j;
        }
    }
    int bc=0;
    for(int i=ec;i;i=fr[i]){bl[++bc]=en[fr[i]]+1;br[bc]=en[i];}
    for(int i=1,j=bc;i<j;i++,j--){swap(bl[i],bl[j]);swap(br[i],br[j]);}
    for(int i=1;i<=qc;i++)an[i]=(V){0,0,0,0};
    for(int b=1;b<=bc;b++){
        int L=bl[b],R=br[b],le=R-L+1,lm=L-1,tc=0,ok=1;
        for(int i=1;i<=le;i++)ta[i]=a[lm+i];
        ds.init(le,ta);
        #define FL() if(tc){if(!ok)sr(tc);int p=0,q=0,r=0;V vv;for(int ii=0,ed=tc;ii<ed;ii++){ds.rt(et[ii],p,q,r,vv);mgto(an[ei[ii]],vv);}tc=0;ok=1;}
        for(int i=1;i<=m;i++){
            int rr=rq[i];
            if(rr<L)continue;
            int llx=lq[i];
            if(llx>R)continue;
            int l=(llx<L)?1:(llx-lm);
            int r=(rr>R)?le:(rr-lm);
            if(tp[i]==1){
                if(l==1&&r==le)ds.all(xq[i]);
                else{FL();ds.add(l,r,xq[i]);}
            }else{
                int id=idq[i];
                if(l==1&&r==le){
                    ll z=ds.gt();
                    if(tc&&et[tc-1]>z)ok=0;
                    et[tc]=z;ei[tc++]=id;
                }else{
                    V vv;
                    ds.qry(l,r,vv);
                    mgto(an[id],vv);
                }
            }
        }
        FL();
        #undef FL
    }
    for(int i=1;i<=qc;i++){wt(an[i].a);pc('\n');}
    fwrite(ob,1,oop,stdout);
    return 0;
}

:::

参考文献

世界上最幸福的女孩和这道题------shadowice1984大佬的两篇题解

还有一个不记得在哪了，是lxl在某个地方发的改版前的题解

写在前面

我们知道“单点修区间最大子段和”用线段树维护四个值：区间和、最大前缀和、最大后缀和、最大子段和，下面分别用 $s/ls/rs/mx$ 表示

这题以前的版本是只加正数，官方解法是先分成 $\sqrt n$ 个块

然后对每个块建一颗凸包线段树，维护 $ls/rs/mx$ 的凸包 (上凸壳)（和$P5073$类似）

凸包的事我想shadowice1984大佬的题解很清晰，这里声明：必须要搞清楚他是怎么$O(N)$合并两个子凸包的

对于覆盖了整棵树的修改，由于加上的是正数，所以指针看情况往后拉就行，复杂度均摊$O(1)$

重点是部分修改，全部重造线段树会让你的代码T掉

这里要搞懂线段树构建的本质，这里以长方形类比，每层长$\sqrt N$，宽$log\sqrt N$

凸包从底层建起，合并信息是$O(\sqrt N)$的，这里的$\sqrt N$为整棵线段树的服务长度即块长

lxl给出的解决方案和第二篇题解一样，是按照线段树基本操作，将操作下传到 $log$ 个子节点

如图，红色部分为修改的区间，同时引起绿色部分的改变，红色部分打上标记日后处理底下的，黑色部分就不用动了

结合$O(\sqrt N)$合并子凸包的操作，我们这次修改的复杂度就是红绿色的长度和

复杂度$/$规模就是$O(k\sqrt N)$------$k$为一巨大常数

搞定了修改操作，询问就变得不堪一击，但值得一提的事，修改操作特别是对懒标记的处理十分繁琐

由于技艺不精，我的常数巨大，T到飞起，先后多次尝试此题，花费大量精力修改代码，均以失败告终

现在给出一个个人觉得方便的处理方法：

线段树只记一个 $c$，表示这一层所有点要加 $c$

下到目标节点时：

if(l<=tr[now].l&&tr[now].r<=r){tr[now].c+=k;return ;}

懒标记下放时也只传个 $c$ 下去

然后上面节点引用下面的点集时

struct point{ll x,y;point operator+(ll const&AK47)const{return point{x,y+AK47*x};}};
point jia(point a,point b){return (point){a.x+b.x,a.y+b.y};}

P=jia(A,B+tr[lc].c);

这样设置比较方便，但要注意运算顺序

正片（很短）

现在难度加大了，可以加负数了。。。唯一不变的还是两个字：分块

但有的东西你想不到就真的想不到了。。。

分块做区间加区间和做过吗？

是不是每个操作都是从左往右，小段----大段----小段，这样？

你试过按块处理问题吗？

就是对第一块扫描$n$个问题，然后再去下一个块

这里就有一个重要的思想，前提是数据可以合并，势能可以均摊(这里很抱歉用了势能，可能不太严谨)

我们知道小段共有 $n$ 个，单次操作复杂度$O(\sqrt n)$

又有大段 $n\sqrt n$ 个，单次操作复杂度$O(1)$

均摊下来每个块的复杂度是$O(n)$的，刚好有$\sqrt n$个块

所以——你懂得，这玩意用在这里真的真的真的，女少口阿

如图，黑色为块的分界，绿色为询问，红色为修改，下面一段字的 $n$ 和 $m$ 表示规模

我们知道，有 $m$ 条红色，就可以通过分块变成 $m$ 条小块的红色，和$m\sqrt n$条整段的红色

又有 $m$ 条绿色，就可以通过分块变成 $m$ 条小块的绿色，和$m\sqrt n$条整段的绿色

其中绿色中的小块我们可以暴力解决

那么对于任意一个块中，就会出现如下情况

不妨设为最坏情况，有最多$m$条绿色大段和最多$m$条红色大段 交错 在一个块里

那红色小段？。。。

大段的总量是红色小段总量的$\sqrt n$倍，即红色小段是极为稀疏的

然后只要把这玩意一圈

天哪这不就是P5073！！？

不说了。。。你们加油 $\color{white}\text{别问为什么没代码，问就是qwq}$

写在后面（雾

去年我看到这题就开始在机房没日没夜的尝试，尝试了好多个3天，都快憋出病了。。。如今终于敲出来了，但是细节超多，RE半天发现自己忘memset，max函数没开long long……

个人感受：lxl的一些题最妙的地方在于“总量一定”，从而达到均摊的复杂度

最后的最后，祝珂朵莉继续幸福下去。

还有，管他什么题总之lxl毒瘤数据结构天下第一！！