差分数组实战：算法竞赛经典题“最高的牛”全解析

1. 问题定位与差分思想的引入很多接触算法竞赛的同学第一次真正感受到差分威力的题目往往就是《算法竞赛进阶指南》里这道最高的牛。它表面上是道和身高有关的应用题骨子里考的却是区间操作的高效处理。如果你刚把前缀和与差分的概念背完正缺一道能打通任督二脉的实战题那这道题再合适不过。先把这个题目本身描述清楚。农场里有 N 头牛站成一排告诉你第 P 头牛是最高的身高为 H除此之外还给了一组关系每一条关系由两个编号 a、b 构成表示a 这头牛能看到 b 这头牛。能看到的意思是在 a 和 b 之间不含两端的所有牛身高都必须严格小于 a 和 b 的身高。换句话说区间内没有任何一头牛的身高超过这两头。现在要求你求出在满足所有给定关系的前提下每头牛可能达到的最高身高分别是多少。初次接触这道题的人通常会走两个弯路。第一个弯路是试图模拟整个身高序列每来一条关系就区间扫描一遍把区间内的牛身高全部减一。这做法很容易想复杂度却高得离谱关系一多就会超时。第二个弯路是把它当成某种排序或拓扑问题绕进谁比谁高的相对关系里出不来。实际上这道题考察的视角非常单一给定一对能互相看见的牛等价于它们中间的所有牛都必须比它们矮也就是说中间这一段整体身高要压低。对一段整体做同样的修改这不就是差分的出场时机吗。理解这一层解题思路就清晰了假设所有牛初始身高都为 H每来一条 (a, b) 关系就把 a 和 b 中间的数字全部减 1。最终用前缀和还原出每头牛的身高答案自然就是在全部约束下每头牛能达到的最高值。为什么这个全部初始化为最大值、遇约束就压低区间的思路是正确的后面我们从数学模型角度详细拆一遍。2. 为什么差分能精准表达最高约束2.1 问题本质上的区间统一步调这道题最核心的思想转换是把关系约束翻译成区间减法操作。我们来看一条关系 (a, b) 的含义假设 a 的编号小于 b。条件说 a 能看到 b那就是说区间 (a, b) 内没有任何一头牛的身高达到 a 或者 b 的身高水平更准确地说这些牛都得比 a、b 都矮。如果我们把每头牛的身高一开始全都定为最大的 H那么当 (a, b) 被声明为可见关系时(a, b) 内部的所有牛都必须低一头也就是全部减 1。这个减 1操作非常符合差分的特性。差分数组里我们要对原数组的 [l, r] 区间统一加一个值 v做法是在差分数组的 l 位置加 v在 r1 位置减 v。对应当前的场景每次关系给出的区间恰好是 [a1, b-1]当 a 小于 b 时在这个区间上整体减 1。如果关系里 a 大于 b只需要交换一下编号保证区间左端点小于右端点再执行同样的操作。使用差分的根本原因在于如果不用差分每处理一条关系就要遍历一次它覆盖的所有位置。假设 N 是 1 万M 是 1 万很多关系都是大跨度区间整体复杂度会到 N 乘 M 的量级这在竞赛时限内根本跑不动。引入了差分数组后任意一次区间操作只需要修改两个点。哪怕有 M 条关系也只需要 O(N M) 的时间这个提升是降维打击式的也正是出题人希望考察的核心能力。2.2 全部置 H 的数学合理性有人会问凭什么一开始把所有牛的身高都设成最高值 H而不是按某种逻辑分配一个初始身高这里需要一点贪心和数学上的对照。题目问的是每头牛可能达到的最高身高那么我们的目标就是从某个足够高的起点出发在各种约束下尽量少地压低每头牛。H 本身是所有牛身高的上界把每头牛的初始值都设为 H相当于先假设所有约束都不存在然后逐条把约束变成区间减法。由于每一对可见关系施加的约束一定是把区间内部压低 1在初始全 H 的方案下并且所有约束都是独立的区间操作那么最后还原出来的序列天然满足所有约束。为什么它一定是最高的我们做一个反证假设存在一个满足所有关系的合法方案其中某头牛身高高于我们还原出的值。还原出的值是 H 减去它被压低的总次数而被压低的总次数等于覆盖它的可见关系数量。要在任何一头牛身上降低被压低的次数就只能减少覆盖它的区间数量而减少任何一个可见关系对应的区间压低都会破坏那条关系成立的前提——区间内必须有牛比端点矮。因此我们的还原值已经是各位置在约束下允许的上确界没有任何合法方案能够给某个位置更高的值这就是差分加初始最大值的方案能得到最优解的根本原因。这个反证法的思路建议在赛场上不需要完整书写但你心里必须想明白你以为你在做的是模拟约束其实是在做一个最大可行解的构造而不是猜答案。想通了这一点这道题从感觉上去做就升级成了逻辑上证明它是正确的底气完全不同。3. 核心代码实现与关键细节3.1 完整实现与逐行注释语言层面这道题用 C 写最方便用 Python 也能过只要注意输入输出效率下面给出 C 的标准写法并逐段解释每一行在做什么。#include bits/stdc.h using namespace std; const int MAXN 10005; int diff[MAXN]; // 差分数组 int ans[MAXN]; // 还原后的身高数组 int main() { int N, P, H, M; cin N P H M; setpairint, int seen; // 用来去重 for (int i 0; i M; i) { int a, b; cin a b; if (a b) swap(a, b); // 关系 (a,b) 表示 a 能看到 b // 区间 (a,b) 内部不能有牛身高达到端点高度因此整体减 1 if (a 1 b - 1) { // 去重同一对关系如果出现过多次只需处理一次 if (seen.count({a, b})) continue; seen.insert({a, b}); diff[a 1] - 1; // 区间起点压低 diff[b] 1; // 区间终点之后恢复 } } // 利用前缀和还原每头牛的身高 for (int i 1; i N; i) { ans[i] ans[i - 1] diff[i]; cout H ans[i] \n; // 初始身高 H加上差分累计值 } return 0; }这段代码里最关键的是 diff 数组的修改方式。我们要给区间 [a1, b-1] 整体减 1按照差分的定义应该在 diff[a1] 处减 1在 (b-1)1 b 处加 1。这里 b 位置加 1 很容易被初学者忽略一旦漏掉前缀和还原出来的数组后半部分就会一直处于被压低的状态。注意这里我们输出的是 H ans[i]因为 ans[i] 记录的是累计的差值而不是最终身高初始身高 H 需要保留并叠加。这里使用 set 去重是出于严谨性考虑。实际题目里关系可能存在重复如果重复处理同一条关系那么区间内所有牛会被重复压低导致结果比正确值低。用 set 存储已经处理过的 pair在输入阶段直接跳过重复项是最省心的写法。如果你担心 set 影响性能也可以把每对关系排序后存入数组最后统一 unique但在大多数 N、M 规模下 set 足够应对。3.2 区间端点计算的常见失误见过太多人在区间端点上犯迷糊这里单独拎出来强调。假设输入是 (a, b)我们默认 a 小于 b那么能够互相看见的两个端点中间是 a1 到 b-1。差分操作必须覆盖这些中间的位置因此修改的是 diff[a1] 和 diff[b]。举个例子a3b7那么区间内部是 4、5、6在 diff[4] 处减 1在 diff[7] 处加 1。还原时4、5、6 三个位置各被压低 17 号位不受影响3 号位也不受影响逻辑完全正确。如果你习惯用前缀和的左加右减来思考注意这里方向是相反的。普通差分是在左端点加、右端点后面减我们做的是减法操作所以左端点减、右端点后面加。方向反了整道题就废了。具体的验证方式很简单拿一个小的测试数据手动模拟一遍马上能看出问题出在哪。另一个容易出错的边界是 a 和 b 相邻的情况也就是 a1 等于 b。此时区间内部没有任何牛理论上这组关系不产生任何约束连差分修改都不需要做。代码里用 if (a 1 b - 1) 把这个情况过滤掉看起来是个小判断实际上能省很多不必要的修改。当然就算你不写这个判断只要正确执行区间计算相邻情况也会因为区间为空而不产生实际影响但写上会让逻辑更清晰。4. 实战变式与同思路扩展4.1 题目变式统计覆盖次数最高的牛解决的是区间减法问题它的镜像场景是区间加法。把问题改一下有一排位置初始值都是 0每次给一个区间 [l, r]要求区间内所有位置加 1最后输出每个位置被加了多少次。这就是纯粹的前缀和模板题。两者的差分操作完全一样只是方向相反。理解了最高的牛的减法思维这类区间加法的题基本上就是顺手解决。真实的竞赛题经常把差分、前缀和与排序、离散化结合起来考察。比如有些题会给出很多区间问哪些位置被覆盖的次数最多。这时你只需要用差分统计区间覆盖次数再用前缀和还原出每个位置的被覆盖次数最后扫描一遍找最大值即可。复杂度是 O(NM)完全不虚大数据量。这种题考的就是你能不能一眼看出区间增量操作是差分的舒适区。4.2 变式区间内加不同值更高阶一点的变式是不止区间统一加减而是区间内每个位置加的值随位置线性变化。这时候朴素的差分就不够用了需要引入二阶差分也就是对差分数组再做一次差分。这在最高的牛这题的延展里并不要求但如果你能把差分的思想吃透遇到这种变式时会自然联想到对差分再差分的处理手法而不会卡在原地。学算法最忌讳的是一个题一个方法像背公式一样套模板。差分本身就是前缀和的逆运算两个方向结合起来的威力远超单个方向。建议你做完最高的牛之后自己试着把题目改成区间内牛的身高加 1再用同样的套路写一遍体会一下加减方向变化对代码的影响比刷五道同类题都管用。4.3 变式二维差分初探如果横向扩展一步差分还可以应用到二维矩阵上。比如有一块矩形区域每次把一个小矩形覆盖的土地整体加一个值最后问每个格子的值是多少。这时需要在二维差分数组的四个角分别做加减操作——左上角加 v、右上角减 v、左下角减 v、右下角加 v然后做两次前缀和恢复。二维差分理解起来比一维抽象一点但本质上和一维一模一样只是每个位置的值受横纵两个方向的影响。矩阵前缀和的公式是 S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]恢复二维差分时也用这个公式。很多同学一看到右上角减 v、左下角减 v、右下角加 v就懵了其实只要记住每个格子的值等于以它为右下角的所有差分项之和推一推就通了。5. 常见错误与排查技巧实录5.1 经典错误一重复关系未去重很多题目为了增加干扰会故意把同一对关系给出多次或者给出等价变体。如果不做去重差分数组就会被反复修改最后还原的高度偏小答案错误。去重的标准做法是用 set 存 pair或者在读入时把 a、b 统一成小号在前再判断是否已存在。有些选手觉得给出的关系重复一下也无妨结果不会差太多这在算法题里是致命伤。数据量小的时候可能侥幸过了数据量一大、重复又多错误值会积累到肉眼可见的程度和正确答案差了不止一个身位。要么在输入阶段去重要么在输出前检查一下有没有覆盖了两次同一区间的异常情况。5.2 经典错误二区间端点搞反方向差分数组加减方向错误是新手最常见的翻车点。记住一句话区间整体减左端点差分减右端点后差分加区间整体加左端点差分加右端点后差分减。方向错一次整个序列就像波浪一样扭曲而且越往后错得越离谱排查起来特别麻烦。这里给一个自测技巧还原出数组后手动验证一条关系 (a,b)看看 a 和 b 之间是不是全部严格小于端点值。如果发现相邻两头牛身高一样或者中间某头牛和端点一样高那问题基本就出在区间处理上。把所有关系的区间端点列出来对照 diff 数组的修改位置纸面推演一遍基本能找到是哪里反了。5.3 经典错误三忘记初始化与溢出初始身高 H 和累计差分值是两个东西输出时必须把 H 加上。见过有人直接输出 ans[i]结果打印出来的全是负数或者 0那显然是把初始身高丢了。另外如果 N 和 M 都很大累计差分值可能出现负数和 H 相加后仍然在合法范围内所以要用 int 甚至 long long 保存。如果你用的是 Cset 去重和差分数组都放在堆上还是栈上并不关键但要注意 ifstream 用 cin 做大数据输入时记得关同步否则容易 TLE。用 scanf 或者 ios::sync_with_stdio(false) 都可以我在实际体验中更推荐后者代码写起来方便性能也足够了。5.4 经验从暴力对比验证思路如果你对差分解法不够自信最笨也最有效的验证方式是写一个暴力程序做对拍。暴力做法最简单直接初始化一个全是 H 的数组每来一条关系就把区间内每个位置减 1最后直接输出结果。随机生成 N 和 M以及合法的关系数据把暴力解和差分解的输出逐行对比几百组数据跑下来如果全对那这个思路基本就没问题了。这个对拍的过程花不了多少时间但对理解题目和建立信心帮助巨大。我见过很多刚开始学差分的同学用对拍验证一次之后才对差分为什么不会出错有了真正直观的认识。所以说这道题值得你多花几分钟做一次对拍比多刷五道题更有价值。6. 从最高的牛延伸到竞赛刷题策略6.1 这道题在算法学习路径中的位置前缀和与差分是许多算法的地基。比如离线处理区间查询问题时经常用到前缀和来快速获取区间和在处理树上路径的修改时也有树上差分的变体。如果你只把最高的牛当成一道独立题不往后面延伸那学到的东西很有限。反过来如果你做题时能意识到这是一次区间操作可以差分优化那么后面学到线段树、树状数组时就会自然地把差分的思想嵌套进去。很多排序、离散化、双指针问题里也藏着差分的影子。比如区间求并、区间覆盖长度都是把区间端点做差分处理再扫描。可以说差分不只是一个单独的算法它是一种观察角度任何区间整体变化的问题都可以想想能不能用两个端点的修改来代替区间的遍历。6.2 如何高效刷前缀和与差分专题建议顺序是先刷几道裸的模板题确认差分和前/后缀还原完全没问题再去挑战带花样的题目。裸题是锻炼肌肉记忆带花样的是锻炼思维方式。最高的牛在进阶指南里被放在差分小节里本身就承担了看似应用题、实为模板题的过渡作用。刷题过程中每道题都自己手写一遍差分推导不要直接抄代码。你可能会发现不同题目里 diff 数组的初始化和最终还原方式有细微区别比如有的题要加偏移量、有的题要从 1 到 N 循环。这些区别背后都是同一个原理真正理解了就不怕变化。6.3 一个适合扩展的后续练习思路做完最高的牛你可以自己变一个问题如果关系规定区间内所有牛身高至少比端点矮 k怎么改答案是把区间内减 1 改成减 k做法完全不变。再把问题改成求每头牛在所有合法方案中的身高范围最小值和最大值那就需要正反各做一遍差分了。这种自己改条件的练习比多找几个类似的题目更训练思维能力也更容易让你在考场上遇到陌生变式时保持冷静。我个人很推荐这种一题多改的学习方法。每改一次你对原题的理解就加深一层。当你能把最高的牛从一个具体题目上升到所有区间统一差值修改都可以用差分的抽象认识那数据结构的基础就算真正打牢了。6.4 总结一个适用面很广的解题反射弧最后分享一个我自己的经验看到区间操作题先问自己几个问题。第一个问题这个操作是不是对整个区间所有位置做相同的变更如果是差分就是首选。第二个问题这个变更是不是多次叠加、最后才需要知道每个位置的值如果是那前缀和还原就顺理成章。第三个问题有没有可能用两个端点的变化来等价代替整个区间如果能那说明你已经进入差分思维了。这三个问题帮我解决过很多看起来完全不像差分模板题的竞赛题。所谓学算法不是背模板而是建立反射弧大概就是这个意思。对最高的牛这道题你如果能通过它建立起这种反射弧那这题的价值就翻倍了。做算法题最重要的不是你背了多少题解而是你看到题目的时候脑子里能自动弹出这题和那个差分模型好像的联想那才是真正的进步。