S与S的无赖同盟（KTT）

Judgelight · 2025-06-15 12:28:57 · 个人记录

一开始还想着“这个文笔，牛逼啊，现在都这么有技术力了吗”，结果一看后记野村美月！对不起长官，刚才没有认出你。

言归正传，虽然我既不是 s 也不是 m 但是这本书确实很有趣，而且恋爱喜剧的成分很重，野村美月老师特有的细腻文笔也表现得淋漓尽致，可以供消遣用。感觉她做得最成功的一点是避免了人物脸谱化，每个人仿佛都没有很浓厚的戏剧效果，说是恋爱喜剧不如说是小故事。

模板

经典问题：单点加区间最大子段和

加强：区间加区间最大子段和（加的都是正数）

原问题的信息维护：s,ls,rs,mx：区间和，包含左端点的最大和，包含右端点的最大和，区间最大子段和

我们考虑区间加对这些操作的影响，如果区间加之后最优的决策点没有发生变化，那么每个值应该可以写成一次函数的形式：kx+b。其中 x 表示区间加的值，k 就是最优决策的区间长度。

为了判断最优决策区间是否发生改变，我们还需要记录一个值 lim 表示如果区间加的累计值 x>lim 则 ls,rs,mx 中至少有一个的决策会发生改变。在实现的时候我们每次给 lim 减去区间加的值，如果 lim<0 那么就暴力递归整个子树进行重构，重构时如果当前节点的 lim\ge 0 则直接返回，否则递归。

关于标记的合并：

1. s=l.s+r.s
2. ls=\max(l.ls,l.s+r.ls)
3. rs=\max(r.rs,r.s+r.rs)
4. mx=\max(l.mx,r.mx,l.rs+r.ls)

其中 \max 的比较依据为一次函数在 x=0 处的值的大小，+ 为一次函数加。

时间复杂度：O((n+m)\log^3 n+q\log n)，其中 n,m 为序列长度和修改次数，q 为询问次数，实际跑起来是大常单 \log 的感觉，因为发明者给出的这个复杂度只是一个粗浅的上界，并没有卡满。

struct Line{int k;ll b;};
inline Line operator+(const Line &a,const Line &b){return (Line){a.k+b.k,a.b+b.b};}
pair<Line,ll>max(Line a,Line b){
    if(a.k<b.k||(a.k==b.k&&a.b<b.b))swap(a,b);
    if(a.b>=b.b)return mk(a,inf);
    return mk(b,(b.b-a.b)/(a.k-b.k));
}
struct Misaka{Line s,ls,rs,mx;ll x;};
inline Misaka operator+(const Misaka &a,const Misaka &b){
    Misaka c;pair<Line,ll>o;
    c.s=a.s+b.s,c.x=min(a.x,b.x);
    o=max(a.ls,a.s+b.ls),c.ls=o.first,c.x=min(c.x,o.second);
    o=max(b.rs,b.s+a.rs),c.rs=o.first,c.x=min(c.x,o.second);
    o=max(a.mx,b.mx),c.x=min(c.x,o.second);
    o=max(o.first,a.rs+b.ls),c.mx=o.first,c.x=min(c.x,o.second);
    return c;
}