这道题我第一次是在一个练题清单里撞见的当时只觉得标题里的最优挤奶挺有意思读完题面才发现它是个非常标准的模型题一排机器各有产量相邻两台不能在同一天启用中间还会不断有人修改某一台的产量要求每次修改后立刻给出当前能拿到的最优总量。关键词就三个——单点修改、相邻互斥、全局最优。看起来像道大水题实际上它把线性 DP 只能离线做这个痛点捅得很透是动态 DP 入门绕不开的一站。适合已经会写线段树、但还没搞明白区间信息怎么合并才能维护最优决策的人也适合想找一道题彻底吃透最大权独立集在序列上的动态维护的读者。下面我按自己当时的推导顺序走一遍从模型抽取、状态设计、合并公式到踩坑清单尽量把每一步为什么这么干讲清楚。1. 题目重述与核心模型抽取1.1 一句话说清题意一排位置一共 n 个每个位置有个数值挤奶量。你要从中挑若干个位置规则只有一条不能同时挑相邻的两个。目标是被挑中位置的数值之和最大。在此之上题目会给出若干次操作操作分两类把某个位置的值改成新值或者询问当前的最优总和。修改是持久的会影响后续所有询问。按照原始题面的规模n 大约在四万级别操作次数在五万级别数值本身是正数且总量可能超过 32 位整型范围这一点后面我会专门讲。输入输出格式在不同版本里有些细节差别有的是每条修改后直接输出有的是单独的询问行所以真正开打之前一定要把题面逐字读一遍别凭记忆写。1.2 把挤奶翻译成图论语言把每个位置看成一个点相邻的两个点之间连一条边整张图就是一条链。要求是挑出的点集里没有两个点相邻这正是图论里独立集的定义再带上点权求最大就是最大权独立集。链上的最大权独立集有个非常经典的性质它可以由左往右一遍线性递推算出来不需要任何复杂的图算法。这一步翻译很重要因为一旦你识别出这就是链上的最大权独立集脑子里立刻能调出对应的 DP 式子也就能判断出这题的静态版本是 O(n) 送分难点全在动态修改上。很多人卡住不是因为不会 DP而是没意识到自己在做的其实是一个被反复重算的 DP。1.3 数据规模倒推算法路线把规模代进去算一笔账如果每次修改之后重新跑一遍线性 DP单次代价 O(n)五万次操作就是 2×10⁹ 量级的加法运算在常见的时间限制下必然超时。这就直接排除了暴力重算这条路。剩下的选择无非几种分块、树状数组套东西、线段树、平衡树。考虑到操作是单点改 全局问而 DP 又是从左到右的线性结构线段树是最自然的匹配——它把序列切成区间每个区间维护一份浓缩后的决策信息修改只影响一条从叶子到根的路径全局答案就放在根上。这里的关键判断是这个 DP 的信息能不能被浓缩成一个常数大小的结构并且支持两段区间拼接。如果能线段树就成立如果不能就得换思路。这道题能而且浓缩得非常漂亮。2. 朴素 DP 为什么撑不住修改代价分析2.1 线性 DP 的正确姿势先把静态版本写对后面所有的动态维护都是以它为基准去对拍的。定义两个状态处理到第 i 个位置时第 i 个位置不选的最大收益记作 dp0第 i 个位置选的最大收益记作 dp1。转移很直白如果第 i 个不选那第 i-1 个选不选都行取两者较大值new0 max(dp0, dp1)如果第 i 个选那第 i-1 个必须不选new1 dp0 a[i]。初始状态是 dp0 0、dp1 负无穷表示第一个位置被选这件事在还没有任何元素时是不可能的。扫完整个序列答案取 max(dp0, dp1)。整个式子只有两个变量非常轻。还有一个更直观的等价写法定义 f[i] 表示前 i 个位置的最优值那么f[i] max(f[i-1], f[i-2] a[i])也就是第 i 个不选或者第 i 个选则 i-1 必不选。这就是大家熟悉的打家劫舍模型。两种写法等价但两状态版本更容易推广到线段树上因为它把边界处选没选这件事显式记录下来了。2.2 单点修改打穿了哪一层问题出在线性 DP 的信息是单向流动的。你改动了第 i 个位置的值dp 数组从第 i 项开始往后全部要重算而前面的部分完全不受影响。这种后缀依赖是线性递推的固有特性你没法只重算一小段就收工。有人会想那我把 dp 数组存下来改的时候从 i 开始往后扫到 n 不就行了这就是 O(n) 每次的做法前面算过扛不住。还有人会想那我预处理前后缀可惜 DP 不是可减的前缀信息没法扣掉也没法简单拼接——因为拼接的时候左半段的最后一个位置和右半段的第一个位置之间有相邻约束你不知道这两个端点的状态就没法把它们的最优值直接相加。这就是所有动态 DP 问题的共同难点局部最优解在拼接处会失效。要解决它必须让每个区间在交出答案的同时把边界状态也一并交代清楚。2.3 线段树合并的本质把递推改造成结合律换个角度想。线段树能维护的东西本质上要求运算是可结合的(A ⊕ B) ⊕ C A ⊕ (B ⊕ C)。加法可以最大值可以但跑一遍 DP不是一个二元运算它是一整段流程。突破口是把一个区间抽象成一个函数——输入是左边界外侧的约束状态输出是右边界外侧的状态和最大收益。两个区间拼起来就是两个函数复合。函数复合天然满足结合律所以可以塞进线段树。只不过这道题的函数定义域和值域都很小都是选/不选两种完全可以枚举成一张小表。这个思路一旦建立你就不是在用线段树维护 DP而是在用线段树维护一个转移矩阵。后者是可推广的后面第 5 节我会用 max-plus 矩阵把这件事讲得更透。3. 节点信息设计为什么是四个状态而不是两个3.1 端点状态是合并的唯一钥匙假设每个节点只存一个数这个区间的最大权独立集。那么合并两个儿子的时候你会立刻卡住——左儿子的最优解可能选了它的右端点右儿子的最优解可能选了它的左端点两个一相加就冲突了。而如果你为了保证不冲突强行让两边都不选端点那又可能丢掉最优解。所以节点必须额外记录端点的选取情况。具体来说一个区间只有两个端点值得关心最左端和最右端。中间的点怎么选对外部世界没有任何影响可以放心地压成一个最大值。这个只暴露边界的思想是这套做法的灵魂信息的压缩不是丢掉细节而是丢掉对外无影响的细节。3.2 四个状态的语义与合法性设节点维护f[a][b]其中 a、b 取 0 或 1a 表示区间左端点是否被选中b 表示区间右端点是否被选中f[a][b]表示在这个约束下区间能取得的最大权和。四个组合正好覆盖所有情况。但要注意左端点选、右端点不选这种组合在长度 ≥ 2 的区间里完全合法在长度等于 1 的区间里却是矛盾的——因为左右端点是同一个位置不可能既选又不选。这一点是整道题最容易翻车的地方后面单独讲。四个状态的取值含义我列一下方便对照状态含义典型取值f[0][0]左右端点都不选至少为 0可以全不选f[0][1]左不选、右选可能为负若权值允许为负f[1][0]左选、右不选同上f[1][1]左右都选需要区间长度 ≥ 23.3 合并公式的逐项推导与化简现在把左儿子记作 L右儿子记作 R。合并后的区间左端点就是 L 的左端点右端点就是 R 的右端点。设合并结果为 C那么 C 的f[a][b]取决于L 的状态是[a][x]R 的状态是[y][b]其中 x 是 L 的右端点状态y 是 R 的左端点状态。约束只有一条L 的右端点和 R 的左端点在原序列里是相邻的所以 x 和 y 不能同时为 1。于是合并式就是C.f[a][b] max over (x, y) 满足 x y 1 的 { L.f[a][x] R.f[y][b] }把它展开成三种情况写代码时按这三项取最大值即可x 0, y 0L.f[a][0] R.f[0][b]x 1, y 0L.f[a][1] R.f[0][b]x 0, y 1L.f[a][0] R.f[1][b]注意 (x1, y1) 这一项被禁止不能加进去。很多人的错误就在这里直接把四项全枚举了只判断了和是否更大忘了加约束结果答案偏大样例还能过因为样例可能恰好不触发一交就 WA。合并的代价是常数级别的四个状态每个状态三次加法一共十几次运算。这也是线段树能扛住五万次操作的根本原因——把 O(n) 的递推压成了 O(1) 的表格乘法。3.4 叶子节点与负无穷的边界处理单个位置的区间左右端点是同一个点所以f[0][0] 0这个位置不选收益零f[1][1] a[i]这个位置选收益就是它的权值f[0][1] f[1][0] 负无穷矛盾状态必须标记为不可达这里用负无穷而不是用 0 或者 a[i]原因是如果填了合法值合并时这些矛盾状态会被当成真实方案参与取最大值最终答案会莫名其妙地偏大一点点。而且这个偏差很难通过看输出发现因为往往只是偶尔大一点。我自己在这上面栽过一次调了半天以为是合并式写错了。负无穷的取值也有讲究。千万不要用LLONG_MIN因为合并时要把它和另一个数相加两次LLONG_MIN相加直接是有符号整数溢出行为未定义本机上可能跑出个 0换个编译器就变成另一个数。稳妥的做法是取一个绝对不可能被真实答案达到、同时加上几次也不会溢出的负数比如-1e18。它的两倍是-2e18远在 64 位整型的表示范围内安全。注意负无穷要够小小到任何合法方案都不可能等于它同时要够大大到多次相加不会溢出。这两个条件缺一不可-1e18在绝大多数题里都满足。4. 完整实现建树、合并、单点修改4.1 存储布局与结构体定义用 1 起始的数组下标建树节点 p 的两个儿子是 2p 和 2p1区间是 [l, r]。每个节点存一个 2×2 的 long long 数组。结构体里别写太花哨的构造函数除非你清楚它会被调用多少次——建树时每个节点都要赋一次初值四万个节点乘四性能上没问题但写成 memset 风格的循环会更稳。const int MAXN 40010; const long long NEG -1000000000000000000LL; // -1e18 struct Node { long long f[2][2]; } tr[MAXN 2]; long long a[MAXN]; int n, m;数组开四倍是标准操作n 到四万四倍就是十六万每个节点四个 8 字节整数总共五百多万字节完全放得下。别开两倍虽然满二叉树两倍够用但线段树的编号方式在非 2 的幂时会超出去这是个经典的低级错误。4.2 pushup 的手写展开合并函数是整个代码的核心我建议手写展开而不是套几层循环一是快二是展开之后约束条件一目了然不容易漏。inline void pushup(int p) { Node cur tr[p]; const Node L tr[p 1], R tr[p 1 | 1]; for (int i 0; i 2; i) { for (int j 0; j 2; j) { long long best NEG; // x0, y0 best std::max(best, L.f[i][0] R.f[0][j]); // x1, y0 best std::max(best, L.f[i][1] R.f[0][j]); // x0, y1 best std::max(best, L.f[i][0] R.f[1][j]); cur.f[i][j] best; } } }三项分别对应上一节列的三种情况第四种 (1,1) 直接不写天然满足约束。这里的负数相加是安全的因为 NEG 取 -1e18两份相加是 -2e18还在 long long 范围内。4.3 建树与单点修改建树就是递归到叶子然后一路 pushup 回来。叶子赋值要严格按 3.4 的规则void build(int p, int l, int r) { if (l r) { tr[p].f[0][0] 0; tr[p].f[1][1] a[l]; tr[p].f[0][1] tr[p].f[1][0] NEG; return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); pushup(p); }单点修改是标准的递归下降到叶子重新赋值回溯时 pushup。注意修改是替换而不是累加这一点要看清楚题面给的是新值不是增量。我见过有人写成a[pos] v样例因为是增量形式恰好过了换个数据就全错。void update(int p, int l, int r, int pos, long long v) { if (l r) { tr[p].f[0][0] 0; tr[p].f[1][1] v; tr[p].f[0][1] tr[p].f[1][0] NEG; return; } int mid (l r) 1; if (pos mid) update(p 1, l, mid, pos, v); else update(p 1 | 1, mid 1, r, pos, v); pushup(p); }把叶子的赋值抽成一个内联函数会更清爽也能避免建树和修改两处初始化不一致这种低级 bug。4.4 答案的取法与整体流程全局的答案在根节点上。因为整个序列的两端没有任何外部约束四个状态都是合法的所以直接取四者最大long long query_all() { const Node root tr[1]; long long ans root.f[0][0]; ans std::max(ans, root.f[0][1]); ans std::max(ans, root.f[1][0]); ans std::max(ans, root.f[1][1]); return ans; }这里有个小细节值得说当所有位置的权值都是正数时f[0][0]就是 0一个都不选所以答案至少是 0。如果题面允许负权值那全不选仍然合法答案也仍然是 0取最大之后自然得出正确结果不需要特判。但如果题目要求必须至少选一个那就要额外小心得单独处理。这道题按原意是非负的所以直接取最大就行。主流程就是读入 n 和数组建树然后逐行读操作遇到修改就调用 update遇到询问就输出 query_all 的结果。如果题面是每次修改后都输出那就在 update 之后直接输出不要等。5. 复杂度、常数与实现层面的取舍5.1 时间与空间账建树是 O(n)每次单点修改走一条从根到叶的路径深度是 ⌈log₂n⌉每层做一次常数级别的合并所以单次修改 O(log n)。总复杂度 O(n m log n)。代入四万和五万大约是四万加上八十万次合并每次合并十来次加法总共一千万次运算以内任何平台都是几十毫秒的量级。空间上是 4n 个节点每节点四个 long long约 5MB完全无压力。对比一下如果你用每次暴力重算是 2×10⁹ 次运算差距是三个数量级——这就是把递推改造成可结合运算带来的收益。5.2 常数优化与替代写法真要说优化有几个点第一把合并写成四个独立的赋值语句去掉循环。四层循环展开之后编译器能更好地调度寄存器实测能快一点但在这道题的数据范围下意义不大可读性反而下降。我一般先用循环写对确认无误后再考虑展开。第二把long long换成int是不行的。n 是四万每个位置的权值即使只有十万总和也能到四亿超过 int 上界如果权值更大溢出是必然的。答案用 long long 存中间值也用 long long别在某个地方偷偷转成 int。第三如果题目真的到了需要卡常的规模可以把节点信息压成一个长度 4 的数组用固定下标访问避免二维数组带来的额外寻址。但这是最后一步不是第一步。5.3 max-plus 矩阵视角另一种等价实现前面说节点是一个函数把这个函数写成矩阵形式就是所谓的 max-plus也叫 (max, ) 半环矩阵。仍然用 dp0、dp1 两个状态从第 i-1 步到第 i 步的转移可以写成[new0] [ 0 0 ] [old0] [new1] [ a[i] -inf ] * [old1]这里的乘法是加法代替乘法、取最大代替求和。验算一下new0 max(old0 0, old1 0) max(old0, old1)对new1 max(old0 a[i], old1 (-inf)) old0 a[i]也对。那么整个区间 [l, r] 的贡献就是矩阵 T_l × T_{l1} × ... × T_r按这个顺序左乘到初始向量上。矩阵乘法满足结合律所以可以用线段树维护区间乘积单点修改就是换掉一个叶子矩阵然后重新乘上去。初始向量取[0, -inf]。这套写法的好处是可扩展性极强如果题目变成相邻最多选 k 个或者选了之后要冷却若干天只需要把状态维度加大矩阵变大线段树的骨架完全不用动。坏处是常数更大k 个状态就是 k³ 的合并代价而且对新手来说不够直观。我的建议是先把 2×2 的显式合并写熟理解透了再上矩阵别一上来就用模板套套完自己都说不清为什么对。6. 踩坑实录这些错我看过也犯过6.1 负无穷初始化引发的血案这是最高频的错误没有之一。表现是小数据能过大数据偶尔偏大而且偏大的幅度不大很难察觉。原因就是叶子的矛盾状态没设成负无穷或者设的负无穷不够小。举一个具体的例子n 2两个位置的权值都是 10。正确答案是 10只能选一个。如果叶子把f[0][1]和f[1][0]都填成了 0那么合并时f[1][1]会算出 20直接错。另一种变体是负无穷取-1。当权值本身比较大时-1加上别的数可能仍然是个看起来还不错的值于是矛盾状态被选中。负无穷要远小于任何可能的真实答案这是判断标准。还有一种更隐蔽的负无穷设置在叶子上是对的但合并时忘了跳过不可达状态导致负无穷一直在传播最后某个本该有值的状态变成了负无穷。这种情况通常表现为答案偏小或者出现巨大的负数。6.2 合并顺序、区间拼接与查询返回这道题只问全局所以不涉及区间查询的拼接问题。但只要你想把它扩展到任意区间询问就会立刻遇到查询会返回若干不连续的节点片段需要按从左到右的顺序依次合并。顺序错了相邻约束就作用到了错误的位置上答案必然错。标准的做法是维护两个累加器左累加器和右累加器递归时如果目标区间完全覆盖当前节点就合并进去部分覆盖时先走左儿子再走右儿子回来的时候左边接在左累加器后面右边接在右累加器前面。最后把两个累加器再合并一次。累加器初值用一个空节点标记合并时遇到空节点直接返回另一个。这套写法不难但很容易在递归返回的顺序上翻车。另一个相关的问题是合并是不可交换的。merge(L, R)和merge(R, L)结果不同因为相邻约束是有方向的。任何地方把两个参数写反都会得到错误但看起来差不多的答案。6.3 症状、原因、修法速查表我把这几年见到的、自己犯过的错误整理成一张表调不出来的时候按图索骥比盯着代码硬看效率高得多症状最可能的原因修法小数据对、大数据偏大叶子矛盾状态没设负无穷或负无穷取值不够小叶子 f[0][1]、f[1][0] 设成 -1e18答案出现巨大负数负无穷太小或合并时没跳过不可达状态导致溢出换 -1e18检查是否有两次负无穷相加答案恰好是最优解的一半左右忘记左儿子右端 右儿子左端不能同时选的约束或漏了某一项对照三项合并式逐条检查修改后答案不变update 里没更新叶子或改了数组没 pushup检查递归边界和回溯路径修改后答案全错把替换写成了累加看题面给的是新值还是增量偶发数组越界线段树只开了 2n开到 4n结果超 int 范围用 int 存了总和全程 long long多组数据第二组开始错树没清空上一组残留重新 build 或者手动清调试的时候我有个很土但有效的办法写一个 O(n) 的暴力版 DP 做对拍。暴力版每次修改后重跑一遍n 取几百随机生成几千组操作两边比对。只要有一组不一致就把这组数据的最小规模手工缩出来然后打印出每一层节点的四个状态逐层对。这个方法看起来笨但定位速度比凭直觉找快得多尤其是合并公式这类看起来都对的错误。提示对拍时不要只随机正数也随机一些 0 和大数能顺带把边界和溢出的问题暴露出来。另外提醒一句如果题面是每次修改后输出当前最优值别忘了每一行都要输出不要在循环外面统一输出。这种格式错误在自测时因为忽略了行数很难发现。7. 模型迁移把这套东西用到别的题上7.1 环形首尾相邻最常见的加强版是把序列接成环也就是第一个和最后一个也视为相邻。这时候原来的合并式不够用了因为根节点的四个状态里f[1][1]左右端点都选会违反首尾约束。标准解法是分类讨论把环破开成链情况一第一个位置不选。此时首尾约束自然消失直接对区间 [2, n] 求最优端点自由取四个状态的最大值。情况二第一个位置选。此时第二个位置和最后一个位置都必须不选答案是第一个位置的权值加上对区间 [3, n-1] 求最优。两种情况取较大值即可。要注意 n 比较小的时候区间会退化比如 n 2、n 3 时 [3, n-1] 是空区间需要单独处理空区间的贡献按 0 算。这类边界我一般是手工列出 n 1 到 4 的情况逐个验证比在纸上空想靠谱。如果改成环 动态修改那就得用支持区间查询的线段树每次修改后分别查两段再合并。查询的写法就是 6.2 里说的双累加器版练一次就会。7.2 强制选或强制不选的询问另一类常见的变体是除了修改还会问如果第 i 个位置必须选或者必须不选最优值是多少。这时候不能简单地把权值调大调小来模拟得真的约束状态。做法是查三段[1, i-1]、位置 i 本身、[i1, n]然后在合并的时候把位置 i 的状态钉死。更省事的做法是把必须选翻译成选它的时候额外加一个极大的奖励最后再把这个奖励减掉这样就能复用原来的代码。这个方法在工程上很常见代价是要小心数值范围——奖励必须足够大大到任何方案都会优先选它但又不能大到溢出。7.3 工程场景里的同类结构跳出题目这个模型在真实系统里其实很常见。凡是资源排他 单点状态变化 全局最优的组合底层都是同一套结构。比如排期问题一段时间内的广告位相邻时段不能连续投放同一种素材每个时段的收益不同运营随时可能调整某个时段的收益预估系统要实时给出最优排期。把时段看成位置收益看成权值相邻互斥就是同一素材不能连投完全对得上。再比如任务调度单线程执行器每个任务执行后需要冷却一个周期任务价值不同任务价值会动态调整要实时知道当前能拿到的最大价值。这就是带冷却的最大权独立集只是冷却期从一个变成了 k 个。再比如缓冲区分配连续的几个缓存槽位相邻槽位不能同时分配给同一个租户每个槽位对不同租户的价值不同租户的价值评估会动态刷新。这些场景的共同点是约束是局部的信息是流式的查询是全局的。只要满足这三条线段树维护边界状态这套思路就能直接搬过去改动量通常只在于状态维度和合并式的细节。8. 我自己写这题时的几个习惯最后说点实际操作层面的东西。我现在写这类题习惯先把静态 DP 写好、跑通、留作对拍工具再动手写线段树。这一步花不了五分钟但能省掉后面大量的怀疑人生——因为一旦对拍挂掉你至少知道是线段树写错了而不是连 DP 都写错了。第二个习惯是写 pushup 之前先在纸上把三项合并式抄一遍写完代码再逐项对照。这个动作很傻但合并式的错误光靠肉眼读代码是真的看不出来因为每一项长得都差不多。第三个习惯是建树和修改共用同一个叶子赋值函数。我见过太多次建树时初始化对了修改时忘了设负无穷的 bug抽成函数之后这种问题就绝迹了。关于负无穷的取值我给一个判断标准取 -1e18 时加上最多 log n 次仍然不会溢出同时它比任何合法答案小至少两个数量级这就够了。如果你的题目权值范围更大按比例调整核心是不溢出和足够小这两条同时成立。还有个个人偏好我不太喜欢在结构体里写构造函数来做初始化因为数组定义的时候会逐个调用四万乘四的节点虽然不算多但写起来不直观。直接在建树和修改里显式赋值代码意图更明确调试时也更容易看出哪个状态忘了设。这类小选择没有对错关键是保持全代码一致——别在一处用构造函数另一处手动赋值那样迟早会出现两套初始化逻辑不一致的问题。写完之后我会手动构造三组数据验一遍n 1 的单点、n 2 的两点、以及一个所有值都相等的中等规模数据。前两个验边界尤其是叶子矛盾状态和答案取法第三个验合并有没有把约束漏掉。三组都过了再上随机对拍基本就稳了。