感觉最近做过一万道这种$^*$原又典的题目，故写一篇笔记记录一下。

$^*$：这种指的是维护区间最大子段和/最大连续子段。

Kadane 算法

其实维护最大子段和的算法是有学名的，如题。

本质上是一个动态规划算法，即对于问题：

给定长度为 $n$ 的数组 $A$，求 $A$ 的连续子段 $[l, r]$ 使得 $\sum_l^j A_i$ 最大。当然这里显然有 $(\exists~i \in [1, n])~~A_i<0$，于是我们不难有 $\mathcal{O}(n)$ 的解法如下：

定义 $f_i$ 是以 $A_i$ 结尾的最大子段和，有转移方程：

这玩意看起来好像过于显然以至于好像大多数人都不知道这个有名字。

区间问题

然后我们不难拓展到区间上，即在原问题的基础上加上单点修改和区间查询。

然后我们不难想到线段树。

考虑线段树维护的是一个幺半群（英文：Monoid），即是一个带有二元运算 $\cdot:M \times M \to M$ 的集合 $M$，符合以下公理：

• 结合律：对于所有 $a, b, c \in M$，有 $a \cdot(b\cdot c)=(a\cdot b) \cdot c$；
• 单位元：存在 $e \in M$，使得任意 $a\in M$，有 $a \cdot e = e \cdot a = a$。

然后我们惊人地发现最大子段和正好满足这个条件！即我们考虑两个维护了最大子段和节点信息的合并：

合并后节点的最大子段和，要么是左节点的最大子段和，要么是右节点的最大子段和，要么是横跨左右节点的一段子段和。

然后我们不难发现，横跨左右节点的子段和，就是左节点的最大后缀和拼上右节点的最大前缀和。

于是我们可以用一个四元组 $(\rm{sum}, \rm{ans}, \rm{pre}, \rm{suf})$ 来维护这个信息，有合并操作 $\rm{res} = \rm{lhs} \cdot \rm{rhs}$ 如下：

然后我们不难定义单位元 $e=(0,-\infty,-\infty,-\infty)$

例题 - P4513 小白逛公园

参考实现：

连续子段

我们运用和上面相似的思想，把「最大子段和」替换为「最大连续出现 1 的长度」，便成了这个玩意。

在这里我们合并的时候不是直接合并，而是判断节点的后缀/前缀连续子段是否等于其本身才能合并，例如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Info operator+(const Info &l, const Info &r) {
    if (l.len == 0)
        return r;
    if (r.len == 0)
        return l;

    Info res = {};
    res.len = l.len + r.len;
    res.sum = l.sum + r.sum;

    res.pre1 = l.pre1;
    if (l.pre1 == l.len)
        res.pre1 += r.pre1;
    res.suf1 = r.suf1;
    if (r.suf1 == r.len)
        res.suf1 += l.suf1;
    res.ans1 = max({l.ans1, r.ans1, l.suf1 + r.pre1});

    res.pre0 = l.pre0;
    if (l.pre0 == l.len)
        res.pre0 += r.pre0;
    res.suf0 = r.suf0;
    if (r.suf0 == r.len)
        res.suf0 += l.suf0;
    res.ans0 = max({l.ans0, r.ans0, l.suf0 + r.pre0});

    return res;
}

这里就是下面例题的合并操作，具体可以看我写的代码。

例题 - P2572 [SCOI2010] 序列操作

参考实现：

感觉差不多写完了🤔，但其实是我困了，睡觉。

以上。