• https://uoj.ac/problem/164

Kimi 居然会做这个题的暴力 https://kimi.moonshot.cn/share/cvaqfgsjc3febjghkqh0，
除了一些细节问题（欧姆定律和电阻公式实际不需要，要开 long long），实际能拿 40 分！

然后注意到本题的这个区间减操作，是不能减成负值的（AI 居然也能注意到？），所以我们还需要支持区间最值操作，而区间赋值操作是可以用区间最值模拟的，具体说来我们需要维护一个双半群，标记合并是：

struct F{LL a0, b0, a1, b1;};
F comp(F r, F l) {
    return F{
        max(l.a0+r.a0,-INFF),
        max(l.b0+r.a0, r.b0),
        max(l.a1,l.a0+r.a1),
        max(l.b1,l.b0+r.a1,r.b1)
    };
}

注意这里历史标记需要当前标记的信息来维护，所以不能开两个线段树分别维护。

https://uoj.ac/submission/745579

Posted by xiaodao
Category: 日常