P3097 这道题放在待做题单里很久了一直没动因为标题里“最优挤奶”看着像道很快就能写完的题。真正促使我去做它是有人在群里说了一句“会了这题线段树维护矩阵那一套基本就入门了”。我当晚就写完了然后调了两个多小时——思路其实很快就有了主要卡住我的是矩阵合并的方向和负无穷的取值这两处各让我 WA答案错误了一次而且都是那种不报错、只是答案偏大偏小的静默错误。这道题的正模型很朴素一排牛棚每个牛棚有固定产奶量相邻两个不能同时开工然后有若干次单点修改每次改完都要重新回答当前能挤到的最大产量。一句话概括——带单点更新的链上最大权独立集。如果你只想要结论那就是线段树套 (max,) 矩阵如果你想知道为什么非得是它、写的时候哪里最容易静默出错这篇可以当个对照检查表用。里面会给出能直接编译运行的代码、手算验证过程以及我踩过的每一个坑。1. 把“不能挨着挤”翻译成链上最大权独立集1.1 从题面抽出真正的模型先把题目里不必要的描述去掉。牛棚的位置给定了顺序1 到 n 排成一条线第 i 个牛棚的产奶量记作 a[i]。约束只有一条相邻的两个牛棚不能同时被选中。目标是让选中的那些牛棚的产奶量之和最大。这就是路径图上的最大权独立集。独立集这个概念在图论里很常见指的是选出一个点集集合内部任意两点之间都没有边。放到这条链上“没有边”翻译过来就是“不能有相邻的两个都被选中”。路径图就是一条链每个点只和左右两个邻居相连。这里值得停一下想想为什么换成一般图就不行了。一般的图上求最大权独立集是 NP 难的规模稍大就没法精确求解。而链上能做靠的是线性结构带来的局部性——第 i 个位置选不选只影响第 i-1 和第 i1 两个位置跟更远的位置无关。这种局部依赖在数学上叫马尔可夫性质它是后面能把 DP 写成矩阵乘法的根本原因。没有这条性质矩阵也好线段树也好都无从谈起。所以看到“一排东西、相邻互斥、求最大和”这类描述脑子里应该立刻跳出两个关键词链上独立集、DP。这道题只是在此基础上加了一层“单点修改”把静态问题变成了动态问题。1.2 O(n) 朴素 DP 的正确性与它必然失败的原因朴素做法非常标准。定义两个状态f[i][0]表示只考虑前 i 个位置、且第 i 个不选时的最大收益f[i][1]表示只考虑前 i 个位置、且第 i 个选时的最大收益转移也很好写第 i 个不选的话第 i-1 个选不选都合法取二者较大值第 i 个选的话第 i-1 个必须不选。f[i][0] max(f[i-1][0], f[i-1][1]) f[i][1] f[i-1][0] a[i]边界是f[0][0] 0、f[0][1] -∞不存在“第 0 个被选中”这种情况。最终答案就是max(f[n][0], f[n][1])。这个 DP 用一个滚动变量就能把空间压到 O(1)时间复杂度 O(n)单次求解非常快。问题出在“单次”两个字上。修改了第 i 个牛棚的产奶量之后从 i 到 n 的所有f值都可能发生变化必须从头重算。最坏情况下改的是第一个位置整条链都要重新推一遍。设操作次数为 m总复杂度就是 O(nm)。按这类题的常见数据规模估一下就大概能看出情况了规模设定单次 DP操作次数总运算量级结果n4×10⁴m4×10⁴4×10⁴4×10⁴约 1.6×10⁹超时n10³m10⁵10³10⁵约 10⁸勉强n4×10⁴m10²4×10⁴10²约 4×10⁶轻松也就是说只要 n 和 m 同时上万这种按链顺序从头到尾重新推一遍的解法就行不通了。真正的诉求是改一个位置只重算受影响的部分并且让“合并两段结果”这件事的代价足够低。2. max-plus 矩阵把一次 DP 递推压缩成一次乘法2.1 普通矩阵乘法为什么不行看到“DP 转移”和“矩阵”很多人的第一反应是构造一个矩阵然后做普通乘法。但普通矩阵乘法的运算是“先乘后加”C[i][j] Σ A[i][k] × B[k][j]。而这里 DP 的运算是“先加后取最大”f[i][1] max(f[i-1][0] a[i], f[i-1][1] (-∞))。运算规则完全不同无法直接套用普通矩阵乘法。正确的做法是换一套运算规则把加法换成取最大把乘法换成加法。这个结构叫做(max, ) 半环也有人叫它 max-plus 代数。在这个半环里“加法”是取最大值单位元是 -∞因为max(x, -∞) x“乘法”是普通加法单位元是 0因为x 0 x这个结构满足分配律a max(b, c) max(ab, ac)也满足结合律。有这两条矩阵乘法该有的性质就都有了连乘的顺序可以任意加括号而结果不变——这正是线段树能派上用场的前提。不是所有 DP 都能这么改造。能这么做的条件是状态数有限且固定转移形式与位置无关或者说每个位置的转移可以单独写成一个矩阵。这道题的状态只有两个所以矩阵是 2×2 的非常干净。2.2 转移矩阵的具体形式与手算验证把每一层的转移写成一个 2×2 矩阵。约定用行向量表示状态v_i [f[i][0], f[i][1]]那么v_i v_{i-1} ⊗ M_i其中⊗表示 (max,) 乘法M_i定义成M_i [ 0 a[i] ] [ 0 -∞ ]逐个位置验算一遍。M_i[0][0]0, M_i[1][0]0这两项对应“第 i 个不选”的转移f[i][0] max(f[i-1][0] M[0][0], f[i-1][1] M[1][0]) max(f[i-1][0] 0, f[i-1][1] 0) max(f[i-1][0], f[i-1][1]) ✓M_i[0][1]a[i], M_i[1][1]-∞这两项对应“第 i 个选”f[i][1] max(f[i-1][0] M[0][1], f[i-1][1] M[1][1]) max(f[i-1][0] a[i], f[i-1][1] (-∞)) f[i-1][0] a[i] ✓完全对上了。那个-∞的作用就是强制排除掉“前一个选了、这一个也选”的非法转移它是整个矩阵里唯一体现约束的地方写错的话整个模型就失效了。有了单点转移整条链的结果就是把所有矩阵乘起来v_n v_0 ⊗ M_1 ⊗ M_2 ⊗ ... ⊗ M_n初值v_0 [0, -∞]。于是原问题变成了维护一个矩阵序列的连乘支持单点替换。这正是线段树的标准应用场景。拿 n3、a[5,3,4] 手算一遍验证。三个矩阵分别是M1 [0 5] M2 [0 3] M3 [0 4] [0 -∞] [0 -∞] [0 -∞]先用 (max,) 规则算M1 ⊗ M2位置计算过程结果[0][0]max(00, 50)5[0][1]max(03, 5(-∞))3[1][0]max(00, (-∞)0)0[1][1]max(03, (-∞)(-∞))3得到[[5,3],[0,3]]再乘 M3位置计算过程结果[0][0]max(50, 30)5[0][1]max(54, 3(-∞))9[1][0]max(00, 30)3[1][1]max(04, 3(-∞))4最后用初值[0, -∞]去乘第一个分量 max(05, (-∞)3) 5第二个分量 max(09, (-∞)4) 9。答案是 9也就是选第 1 个和第 3 个549。手工验算无误。3. 线段树维护矩阵连乘合并方向钉死才不会翻车3.1 节点存什么、怎么 pushup、查询取哪个元素线段树的每个节点对应一段连续区间节点里存的是这段区间所有矩阵按顺序乘起来的结果。设节点 p 管辖 [l, r]左儿子管 [l, mid]右儿子管 [mid1, r]那么tree[p] tree[2p] ⊗ tree[2p1]注意这里的方向。tree[2p]代表左边那段必须放在乘号的左边tree[2p1]代表右边那段放在右边。之所以强调是因为(max,) 矩阵乘法不满足交换律写反了结果一定不对。我第一遍就在这里出过错。当时图省事写了个对称的合并本地随手造了几组数据跑居然都过了——因为手造的数据里 a 值都差不多左边乘以右边和右边乘以左边得到的结果在一部分数据上碰巧一致。后来换了一组首尾差异很大的数据立刻暴露出错误。教训是测试数据一定要造首尾不对称的比如 a [1, 1, 1, 1000] 这种一旦顺序反了答案会立刻变成明显不合理的值。至于最终答案取哪个元素因为初值是v_0 [0, -∞]v_n[0] v_0[0] P[0][0] 或 v_0[1] P[1][0] max(0 P[0][0], (-∞) P[1][0]) P[0][0] v_n[1] max(0 P[0][1], (-∞) P[1][1]) P[0][1]所以根节点矩阵的答案就是max(P[0][0], P[0][1])。注意只取第一行的两个元素第二行整体都不参与最终回答——因为第二行对应的是“假想的第 0 个被选中”这种不存在的初始状态。3.2 一份可以直接编译运行的完整实现下面这份代码是我现在用的版本注释比较全改了输入输出格式就能直接提交。负无穷取-1e9理由在第五节详细说明。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 40005; const ll NEG -1000000000LL; // -1e9 struct Mat { ll a[2][2]; }; // (max, ) 矩阵乘法 Mat mul(const Mat A, const Mat B) { Mat C; for (int i 0; i 2; i) { for (int j 0; j 2; j) { C.a[i][j] NEG; for (int k 0; k 2; k) { ll v A.a[i][k] B.a[k][j]; if (v C.a[i][j]) C.a[i][j] v; } } } return C; } int n, m; ll val[MAXN]; Mat tree[MAXN 2]; // 第 i 个位置的转移矩阵 Mat leafMat(ll w) { Mat t; t.a[0][0] 0; t.a[0][1] w; t.a[1][0] 0; t.a[1][1] NEG; return t; } void build(int p, int l, int r) { if (l r) { tree[p] leafMat(val[l]); return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); tree[p] mul(tree[p 1], tree[p 1 | 1]); // 左在左右在右 } void update(int p, int l, int r, int pos, ll w) { if (l r) { tree[p] leafMat(w); return; } int mid (l r) 1; if (pos mid) update(p 1, l, mid, pos, w); else update(p 1 | 1, mid 1, r, pos, w); tree[p] mul(tree[p 1], tree[p 1 | 1]); } int main() { scanf(%d %d, n, m); for (int i 1; i n; i) scanf(%lld, val[i]); build(1, 1, n); ll answerSum 0; // 所有输出的累加和 while (m--) { int pos; ll w; scanf(%d %lld, pos, w); update(1, 1, n, pos, w); ll best max(tree[1].a[0][0], tree[1].a[0][1]); printf(%lld\n, best); answerSum best; } printf(%lld\n, answerSum); return 0; }这份代码里几个关键点leafMat里四个元素的位置一一对应前面推的转移矩阵build和update里的合并顺序严格是“左儿子在前”主循环每次更新后立刻取根节点第一行的较大值输出同时累加到总和里。3.3 建树与修改的常数优化细节这道题的数据规模不算大上面这份代码直接交是能过的但如果想稳一点有几个地方可以调整。第一矩阵结构体里的数组是固定长度的编译器一般能把它编译成寄存器操作别改成vector或者动态分配那样反而慢。第二mul函数里我用了三层循环实际数据规模下编译器会自动展开不需要手工展开成八个赋值手工展开不但难维护出错概率还高。第三如果题目是多组数据注意tree数组每次必须重建不要指望build覆盖全部节点——如果上一组的 n 比这一组大那么编号超过4n的那部分节点还残留着上一组的数据。虽然本题不涉及但这个坑很常见。另外线段树数组开到4n是稳妥的。有人喜欢开2n然后按完全二叉树的编号去算那种写法在建树时要特殊处理容易在边界上出错不推荐。多开一倍的空间换来的是不用思考很划算。4. 另一套等价写法区间端点状态矩阵4.1 端点状态矩阵的定义与合并公式推导前面那套写法是从“转移矩阵连乘”推出来的。其实还有另一种写法很多题解走的是那条路理解它是很有必要的因为两套写法在某些细节上给出不同的答案表达式看不懂就会怀疑自己。这套写法的思路是每个线段树节点直接维护“这个区间内左端点选或不选、右端点选或不选”四种情况下的最大收益。设节点的矩阵为GG[i][j]表示左端点状态为 i、右端点状态为 j 时区间内的最大收益i 和 j 取值 0不选或 1选。叶子节点很好写区间长度为 1左右端点是同一个位置。G[0][0] 0 // 不选 G[1][1] a[i] // 选 G[0][1] G[1][0] -∞ // 左端状态和右端状态冲突非法合并两个相邻区间时需要枚举左区间的右端点状态 k 和右区间的左端点状态 l并且要求这两个状态不能同时为 1因为它们是相邻的两个位置。所以H[i][j] max { G_left[i][k] G_right[l][j] } 条件是 k 和 l 不能同时为 1展开就是把三项取最大H[i][j] max( G_left[i][0] G_right[0][j], // 中间两点都不选 G_left[i][0] G_right[1][j], // 左区间右端点不选右区间左端点选 G_left[i][1] G_right[0][j] // 左区间右端点选右区间左端点不选 )仔细看这个合并其实是 (max,) 乘法的一个变体。如果把右区间的第一行“吸收”掉第二行因为k0时l可以为 0 或 1都可以取等价于max(G[0][j], G[1][j])那它就退化成了标准的 (max,) 乘法。这也说明了两种写法在本质上是一回事只是把边界条件的处理放在了不同的地方。我个人更倾向于用转移矩阵那套原因很简单矩阵的形式由题目的转移直接决定改了约束只改矩阵整个框架不用动。端点状态矩阵那套在合并时多了一层对“相邻”的处理改题的时候容易漏。4.2 为什么答案有时写成 max 四个元素有时只取两个这是最容易让人困惑的地方。用转移矩阵写法时答案是max(P[0][0], P[0][1])只取两个元素。用端点状态矩阵写法时答案往往是max(G[0][0], G[0][1], G[1][0], G[1][1])取四个。为什么不同原因是初始状态的处理方式不同。转移矩阵写法里v_0 [0, -∞]把“假想的第 0 个位置必须不选”这个条件固定下来所以最终只有第一行的元素有意义。而端点状态矩阵写法里整条链的最左端和最右端都是真实位置选不选都合法所以四个都要看。拿 n3、a[5,3,4] 手算一下端点矩阵验证最终结果一致状态 (左,右)含义最优方案收益(0,0)两端都不选只选中间3(0,1)左不选、右选只选右端4(1,0)左选、右不选只选左端5(1,1)两端都选左端 右端9四个取最大得 9和前面转移矩阵算出来的结果一致。注意(1,1)这个状态是最优的这一现象很说明问题——如果只看(0,0)和(1,1)或者只看对角线都会出错所以端点矩阵写法的答案必须是四个元素取最大。反过来说如果你用的是转移矩阵写法答案却写成取四个元素虽然结果也是对的第二行元素不会超过第一行因为初值里-∞的存在但它掩盖了逻辑下次改题容易出问题。建议按照自己用的那套写法老老实实取对应的元素。5. 调试实录-1e18、初值与那些静默出错的细节5.1 负无穷选小了会溢出选大了会污染结果这是我在这个模型上踩过最隐蔽的一个坑值得单独拎出来说。第一版代码里我照着很多题解的习惯把NEG定义成-1e18。本地小数据跑得好好的交上去大面积 WA把负无穷改成-1试试反而过了几组。折腾了很久才想明白问题的根源。在 (max,) 乘法里负无穷是会被累加的。两个-1e18相加就变成-2e18三个就是-3e18。long long的表示范围大约是±9.2×10^18如果一条路径上连续乘了 10 个含-1e18的矩阵累加值就超出范围了发生溢出结果是未定义的。更麻烦的是溢出产生的错误值可能是正数于是它反而被 max 选中答案就直接离谱了。反过来把NEG取成-1也不行。因为真实答案可能为 0比如所有 a[i] 都是 0这时候-1和真实值混在一起虽然大部分情况还能区分但一旦矩阵里有0 (-1) -1这种取 max 时就可能选中一个本该被排除的非法路径。正确的取值应该满足两个条件足够小小到不可能被当成合法答案又足够大大到大数量级累加之后仍然不溢出。设答案的最大值为MaxAns那么NEG MaxAns 0保证任何含非法路径的结果都不可能被选中。同时设乘法的最大累加次数为 K要求K × NEG不溢出即|NEG| × K 9.2×10^18。按常见数据规模MaxAns大约在4×10^4 × 10^5 4×10^9左右具体取决于 a[i] 的上限乘法链长度不超过 n取 K 4×10^4。那么NEG 取值是否会被误选最大累加绝对值是否溢出-1会不够小4×10⁴不溢出但危险-1e9不会4×10¹³不溢出安全-1e15不会4×10¹⁹溢出-1e18不会4×10²²严重溢出所以-1e9是一个非常甜的点。我在代码里就是这么取的。不过还有一种更稳妥的写法在mul里先判断操作数是不是负无穷如果是就跳过这一项。这样无论NEG取多小都不会累加。代价是多一次比较性能影响可以忽略。我个人倾向于 
长河君 · 2026/11/3 23:22:31 · 阅读 1.2k 线段树维护max-plus矩阵解决链上最大权独立集单点修改
P3097 这道题放在待做题单里很久了一直没动因为标题里“最优挤奶”看着像道很快就能写完的题。真正促使我去做它是有人在群里说了一句“会了这题线段树维护矩阵那一套基本就入门了”。我当晚就写完了然后调了两个多小时——思路其实很快就有了主要卡住我的是矩阵合并的方向和负无穷的取值这两处各让我 WA答案错误了一次而且都是那种不报错、只是答案偏大偏小的静默错误。这道题的正模型很朴素一排牛棚每个牛棚有固定产奶量相邻两个不能同时开工然后有若干次单点修改每次改完都要重新回答当前能挤到的最大产量。一句话概括——带单点更新的链上最大权独立集。如果你只想要结论那就是线段树套 (max,) 矩阵如果你想知道为什么非得是它、写的时候哪里最容易静默出错这篇可以当个对照检查表用。里面会给出能直接编译运行的代码、手算验证过程以及我踩过的每一个坑。1. 把“不能挨着挤”翻译成链上最大权独立集1.1 从题面抽出真正的模型先把题目里不必要的描述去掉。牛棚的位置给定了顺序1 到 n 排成一条线第 i 个牛棚的产奶量记作 a[i]。约束只有一条相邻的两个牛棚不能同时被选中。目标是让选中的那些牛棚的产奶量之和最大。这就是路径图上的最大权独立集。独立集这个概念在图论里很常见指的是选出一个点集集合内部任意两点之间都没有边。放到这条链上“没有边”翻译过来就是“不能有相邻的两个都被选中”。路径图就是一条链每个点只和左右两个邻居相连。这里值得停一下想想为什么换成一般图就不行了。一般的图上求最大权独立集是 NP 难的规模稍大就没法精确求解。而链上能做靠的是线性结构带来的局部性——第 i 个位置选不选只影响第 i-1 和第 i1 两个位置跟更远的位置无关。这种局部依赖在数学上叫马尔可夫性质它是后面能把 DP 写成矩阵乘法的根本原因。没有这条性质矩阵也好线段树也好都无从谈起。所以看到“一排东西、相邻互斥、求最大和”这类描述脑子里应该立刻跳出两个关键词链上独立集、DP。这道题只是在此基础上加了一层“单点修改”把静态问题变成了动态问题。1.2 O(n) 朴素 DP 的正确性与它必然失败的原因朴素做法非常标准。定义两个状态f[i][0]表示只考虑前 i 个位置、且第 i 个不选时的最大收益f[i][1]表示只考虑前 i 个位置、且第 i 个选时的最大收益转移也很好写第 i 个不选的话第 i-1 个选不选都合法取二者较大值第 i 个选的话第 i-1 个必须不选。f[i][0] max(f[i-1][0], f[i-1][1]) f[i][1] f[i-1][0] a[i]边界是f[0][0] 0、f[0][1] -∞不存在“第 0 个被选中”这种情况。最终答案就是max(f[n][0], f[n][1])。这个 DP 用一个滚动变量就能把空间压到 O(1)时间复杂度 O(n)单次求解非常快。问题出在“单次”两个字上。修改了第 i 个牛棚的产奶量之后从 i 到 n 的所有f值都可能发生变化必须从头重算。最坏情况下改的是第一个位置整条链都要重新推一遍。设操作次数为 m总复杂度就是 O(nm)。按这类题的常见数据规模估一下就大概能看出情况了规模设定单次 DP操作次数总运算量级结果n4×10⁴m4×10⁴4×10⁴4×10⁴约 1.6×10⁹超时n10³m10⁵10³10⁵约 10⁸勉强n4×10⁴m10²4×10⁴10²约 4×10⁶轻松也就是说只要 n 和 m 同时上万这种按链顺序从头到尾重新推一遍的解法就行不通了。真正的诉求是改一个位置只重算受影响的部分并且让“合并两段结果”这件事的代价足够低。2. max-plus 矩阵把一次 DP 递推压缩成一次乘法2.1 普通矩阵乘法为什么不行看到“DP 转移”和“矩阵”很多人的第一反应是构造一个矩阵然后做普通乘法。但普通矩阵乘法的运算是“先乘后加”C[i][j] Σ A[i][k] × B[k][j]。而这里 DP 的运算是“先加后取最大”f[i][1] max(f[i-1][0] a[i], f[i-1][1] (-∞))。运算规则完全不同无法直接套用普通矩阵乘法。正确的做法是换一套运算规则把加法换成取最大把乘法换成加法。这个结构叫做(max, ) 半环也有人叫它 max-plus 代数。在这个半环里“加法”是取最大值单位元是 -∞因为max(x, -∞) x“乘法”是普通加法单位元是 0因为x 0 x这个结构满足分配律a max(b, c) max(ab, ac)也满足结合律。有这两条矩阵乘法该有的性质就都有了连乘的顺序可以任意加括号而结果不变——这正是线段树能派上用场的前提。不是所有 DP 都能这么改造。能这么做的条件是状态数有限且固定转移形式与位置无关或者说每个位置的转移可以单独写成一个矩阵。这道题的状态只有两个所以矩阵是 2×2 的非常干净。2.2 转移矩阵的具体形式与手算验证把每一层的转移写成一个 2×2 矩阵。约定用行向量表示状态v_i [f[i][0], f[i][1]]那么v_i v_{i-1} ⊗ M_i其中⊗表示 (max,) 乘法M_i定义成M_i [ 0 a[i] ] [ 0 -∞ ]逐个位置验算一遍。M_i[0][0]0, M_i[1][0]0这两项对应“第 i 个不选”的转移f[i][0] max(f[i-1][0] M[0][0], f[i-1][1] M[1][0]) max(f[i-1][0] 0, f[i-1][1] 0) max(f[i-1][0], f[i-1][1]) ✓M_i[0][1]a[i], M_i[1][1]-∞这两项对应“第 i 个选”f[i][1] max(f[i-1][0] M[0][1], f[i-1][1] M[1][1]) max(f[i-1][0] a[i], f[i-1][1] (-∞)) f[i-1][0] a[i] ✓完全对上了。那个-∞的作用就是强制排除掉“前一个选了、这一个也选”的非法转移它是整个矩阵里唯一体现约束的地方写错的话整个模型就失效了。有了单点转移整条链的结果就是把所有矩阵乘起来v_n v_0 ⊗ M_1 ⊗ M_2 ⊗ ... ⊗ M_n初值v_0 [0, -∞]。于是原问题变成了维护一个矩阵序列的连乘支持单点替换。这正是线段树的标准应用场景。拿 n3、a[5,3,4] 手算一遍验证。三个矩阵分别是M1 [0 5] M2 [0 3] M3 [0 4] [0 -∞] [0 -∞] [0 -∞]先用 (max,) 规则算M1 ⊗ M2位置计算过程结果[0][0]max(00, 50)5[0][1]max(03, 5(-∞))3[1][0]max(00, (-∞)0)0[1][1]max(03, (-∞)(-∞))3得到[[5,3],[0,3]]再乘 M3位置计算过程结果[0][0]max(50, 30)5[0][1]max(54, 3(-∞))9[1][0]max(00, 30)3[1][1]max(04, 3(-∞))4最后用初值[0, -∞]去乘第一个分量 max(05, (-∞)3) 5第二个分量 max(09, (-∞)4) 9。答案是 9也就是选第 1 个和第 3 个549。手工验算无误。3. 线段树维护矩阵连乘合并方向钉死才不会翻车3.1 节点存什么、怎么 pushup、查询取哪个元素线段树的每个节点对应一段连续区间节点里存的是这段区间所有矩阵按顺序乘起来的结果。设节点 p 管辖 [l, r]左儿子管 [l, mid]右儿子管 [mid1, r]那么tree[p] tree[2p] ⊗ tree[2p1]注意这里的方向。tree[2p]代表左边那段必须放在乘号的左边tree[2p1]代表右边那段放在右边。之所以强调是因为(max,) 矩阵乘法不满足交换律写反了结果一定不对。我第一遍就在这里出过错。当时图省事写了个对称的合并本地随手造了几组数据跑居然都过了——因为手造的数据里 a 值都差不多左边乘以右边和右边乘以左边得到的结果在一部分数据上碰巧一致。后来换了一组首尾差异很大的数据立刻暴露出错误。教训是测试数据一定要造首尾不对称的比如 a [1, 1, 1, 1000] 这种一旦顺序反了答案会立刻变成明显不合理的值。至于最终答案取哪个元素因为初值是v_0 [0, -∞]v_n[0] v_0[0] P[0][0] 或 v_0[1] P[1][0] max(0 P[0][0], (-∞) P[1][0]) P[0][0] v_n[1] max(0 P[0][1], (-∞) P[1][1]) P[0][1]所以根节点矩阵的答案就是max(P[0][0], P[0][1])。注意只取第一行的两个元素第二行整体都不参与最终回答——因为第二行对应的是“假想的第 0 个被选中”这种不存在的初始状态。3.2 一份可以直接编译运行的完整实现下面这份代码是我现在用的版本注释比较全改了输入输出格式就能直接提交。负无穷取-1e9理由在第五节详细说明。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 40005; const ll NEG -1000000000LL; // -1e9 struct Mat { ll a[2][2]; }; // (max, ) 矩阵乘法 Mat mul(const Mat A, const Mat B) { Mat C; for (int i 0; i 2; i) { for (int j 0; j 2; j) { C.a[i][j] NEG; for (int k 0; k 2; k) { ll v A.a[i][k] B.a[k][j]; if (v C.a[i][j]) C.a[i][j] v; } } } return C; } int n, m; ll val[MAXN]; Mat tree[MAXN 2]; // 第 i 个位置的转移矩阵 Mat leafMat(ll w) { Mat t; t.a[0][0] 0; t.a[0][1] w; t.a[1][0] 0; t.a[1][1] NEG; return t; } void build(int p, int l, int r) { if (l r) { tree[p] leafMat(val[l]); return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); tree[p] mul(tree[p 1], tree[p 1 | 1]); // 左在左右在右 } void update(int p, int l, int r, int pos, ll w) { if (l r) { tree[p] leafMat(w); return; } int mid (l r) 1; if (pos mid) update(p 1, l, mid, pos, w); else update(p 1 | 1, mid 1, r, pos, w); tree[p] mul(tree[p 1], tree[p 1 | 1]); } int main() { scanf(%d %d, n, m); for (int i 1; i n; i) scanf(%lld, val[i]); build(1, 1, n); ll answerSum 0; // 所有输出的累加和 while (m--) { int pos; ll w; scanf(%d %lld, pos, w); update(1, 1, n, pos, w); ll best max(tree[1].a[0][0], tree[1].a[0][1]); printf(%lld\n, best); answerSum best; } printf(%lld\n, answerSum); return 0; }这份代码里几个关键点leafMat里四个元素的位置一一对应前面推的转移矩阵build和update里的合并顺序严格是“左儿子在前”主循环每次更新后立刻取根节点第一行的较大值输出同时累加到总和里。3.3 建树与修改的常数优化细节这道题的数据规模不算大上面这份代码直接交是能过的但如果想稳一点有几个地方可以调整。第一矩阵结构体里的数组是固定长度的编译器一般能把它编译成寄存器操作别改成vector或者动态分配那样反而慢。第二mul函数里我用了三层循环实际数据规模下编译器会自动展开不需要手工展开成八个赋值手工展开不但难维护出错概率还高。第三如果题目是多组数据注意tree数组每次必须重建不要指望build覆盖全部节点——如果上一组的 n 比这一组大那么编号超过4n的那部分节点还残留着上一组的数据。虽然本题不涉及但这个坑很常见。另外线段树数组开到4n是稳妥的。有人喜欢开2n然后按完全二叉树的编号去算那种写法在建树时要特殊处理容易在边界上出错不推荐。多开一倍的空间换来的是不用思考很划算。4. 另一套等价写法区间端点状态矩阵4.1 端点状态矩阵的定义与合并公式推导前面那套写法是从“转移矩阵连乘”推出来的。其实还有另一种写法很多题解走的是那条路理解它是很有必要的因为两套写法在某些细节上给出不同的答案表达式看不懂就会怀疑自己。这套写法的思路是每个线段树节点直接维护“这个区间内左端点选或不选、右端点选或不选”四种情况下的最大收益。设节点的矩阵为GG[i][j]表示左端点状态为 i、右端点状态为 j 时区间内的最大收益i 和 j 取值 0不选或 1选。叶子节点很好写区间长度为 1左右端点是同一个位置。G[0][0] 0 // 不选 G[1][1] a[i] // 选 G[0][1] G[1][0] -∞ // 左端状态和右端状态冲突非法合并两个相邻区间时需要枚举左区间的右端点状态 k 和右区间的左端点状态 l并且要求这两个状态不能同时为 1因为它们是相邻的两个位置。所以H[i][j] max { G_left[i][k] G_right[l][j] } 条件是 k 和 l 不能同时为 1展开就是把三项取最大H[i][j] max( G_left[i][0] G_right[0][j], // 中间两点都不选 G_left[i][0] G_right[1][j], // 左区间右端点不选右区间左端点选 G_left[i][1] G_right[0][j] // 左区间右端点选右区间左端点不选 )仔细看这个合并其实是 (max,) 乘法的一个变体。如果把右区间的第一行“吸收”掉第二行因为k0时l可以为 0 或 1都可以取等价于max(G[0][j], G[1][j])那它就退化成了标准的 (max,) 乘法。这也说明了两种写法在本质上是一回事只是把边界条件的处理放在了不同的地方。我个人更倾向于用转移矩阵那套原因很简单矩阵的形式由题目的转移直接决定改了约束只改矩阵整个框架不用动。端点状态矩阵那套在合并时多了一层对“相邻”的处理改题的时候容易漏。4.2 为什么答案有时写成 max 四个元素有时只取两个这是最容易让人困惑的地方。用转移矩阵写法时答案是max(P[0][0], P[0][1])只取两个元素。用端点状态矩阵写法时答案往往是max(G[0][0], G[0][1], G[1][0], G[1][1])取四个。为什么不同原因是初始状态的处理方式不同。转移矩阵写法里v_0 [0, -∞]把“假想的第 0 个位置必须不选”这个条件固定下来所以最终只有第一行的元素有意义。而端点状态矩阵写法里整条链的最左端和最右端都是真实位置选不选都合法所以四个都要看。拿 n3、a[5,3,4] 手算一下端点矩阵验证最终结果一致状态 (左,右)含义最优方案收益(0,0)两端都不选只选中间3(0,1)左不选、右选只选右端4(1,0)左选、右不选只选左端5(1,1)两端都选左端 右端9四个取最大得 9和前面转移矩阵算出来的结果一致。注意(1,1)这个状态是最优的这一现象很说明问题——如果只看(0,0)和(1,1)或者只看对角线都会出错所以端点矩阵写法的答案必须是四个元素取最大。反过来说如果你用的是转移矩阵写法答案却写成取四个元素虽然结果也是对的第二行元素不会超过第一行因为初值里-∞的存在但它掩盖了逻辑下次改题容易出问题。建议按照自己用的那套写法老老实实取对应的元素。5. 调试实录-1e18、初值与那些静默出错的细节5.1 负无穷选小了会溢出选大了会污染结果这是我在这个模型上踩过最隐蔽的一个坑值得单独拎出来说。第一版代码里我照着很多题解的习惯把NEG定义成-1e18。本地小数据跑得好好的交上去大面积 WA把负无穷改成-1试试反而过了几组。折腾了很久才想明白问题的根源。在 (max,) 乘法里负无穷是会被累加的。两个-1e18相加就变成-2e18三个就是-3e18。long long的表示范围大约是±9.2×10^18如果一条路径上连续乘了 10 个含-1e18的矩阵累加值就超出范围了发生溢出结果是未定义的。更麻烦的是溢出产生的错误值可能是正数于是它反而被 max 选中答案就直接离谱了。反过来把NEG取成-1也不行。因为真实答案可能为 0比如所有 a[i] 都是 0这时候-1和真实值混在一起虽然大部分情况还能区分但一旦矩阵里有0 (-1) -1这种取 max 时就可能选中一个本该被排除的非法路径。正确的取值应该满足两个条件足够小小到不可能被当成合法答案又足够大大到大数量级累加之后仍然不溢出。设答案的最大值为MaxAns那么NEG MaxAns 0保证任何含非法路径的结果都不可能被选中。同时设乘法的最大累加次数为 K要求K × NEG不溢出即|NEG| × K 9.2×10^18。按常见数据规模MaxAns大约在4×10^4 × 10^5 4×10^9左右具体取决于 a[i] 的上限乘法链长度不超过 n取 K 4×10^4。那么NEG 取值是否会被误选最大累加绝对值是否溢出-1会不够小4×10⁴不溢出但危险-1e9不会4×10¹³不溢出安全-1e15不会4×10¹⁹溢出-1e18不会4×10²²严重溢出所以-1e9是一个非常甜的点。我在代码里就是这么取的。不过还有一种更稳妥的写法在mul里先判断操作数是不是负无穷如果是就跳过这一项。这样无论NEG取多小都不会累加。代价是多一次比较性能影响可以忽略。我个人倾向于