增减序列这道题是我认为学习差分数组时最值得反复琢磨的一道入门题。题面看起来很简单——每次选一个区间整体加一或减一问最少操作几次能让整个序列所有数相等以及在最少操作次数下最终能有多少种结果。但越简单的题面越考验思维的转换为什么一个区间题最后会变成差分数组两个端点的配对问题为什么答案不是模拟出来的而是从差分数组的正负盈余直接算出来的这篇文章我想把整条思考链路完整走一遍包括我最早踩过的几个坑。不管你是刚学差分数组的初学者还是已经会写模板但没想通“最终结果种数”这个结论的人应该都能从这里拿到一些比答案本身更有用的东西。1. 先把题面翻译成人话1.1 题目到底要你回答什么先明确一下输入和输出。你拿到一个长度为 n 的整数序列允许的操作是每次选择一个区间 [l, r]把这个区间里的所有数都加 1或者都减 1。目标是让整个序列的所有元素变成同一个值。你需要回答两件事第一最少操作多少次第二在达到最少操作次数的情况下最终这个“同一个值”有多少种可能的取法。很多人第一眼会觉得第二问是多余的因为直觉上所有数都变成同一个值那还能有几种我举个例子你马上就能感受到。序列是 [1, 2, 3]两步操作就能让它全相等先操作区间 [2, 3] 减 1得到 [1, 1, 2]再操作区间 [3, 3] 减 1得到 [1, 1, 1]最终值是 1。但你也可以两步做到另一个结果先操作区间 [1, 1] 加 1得到 [2, 2, 3]再操作区间 [1, 2] 加 1得到 [3, 3, 3]最终值是 3。同一个序列、同样的最少操作次数最终值居然能不一样。所以第二问不是随便问的它背后有一个非常精巧的结构。1.2 为什么模拟一定不是正路拿到这道题第一反应可能是模拟。但很快就会发现两条死路第一序列长度常常能到十万甚至更高一个区间操作影响的是一整段数每次都真的把区间里的数全部加一或减一光是操作本身就很昂贵第二也是更致命的一点我们根本不知道最少需要多少次操作。你要证明“我找到的方案已经最少”就必须有一个理论依据而不是靠枚举或者跑出个结果就觉得对了。这道题命中了算法思维的经典套路当一个操作是“对区间整体生效”时真正发生变化的信息往往只集中在边界上。区间内部所有数的相对关系完全没变变的只是区间左端点和右端点之外的那两个连接处。如果能找到一种表示方法把区间操作压缩成常数次修改那么复杂度就从 O(n) 降到了 O(1)整套分析也就有了抓手。这个表示方法就是差分数组。2. 差分数组把一次区间操作压缩成两个点的修改2.1 从一个数列到一串“相邻差”差分数组的定义很朴素对于原数组 a[1] 到 a[n]构造 d[1] a[1]然后 d[i] a[i] - a[i-1]i 从 2 到 n。为了后面讨论方便我们再补一个哨兵位置 d[n1] -a[n]这样整个差分数组的总和恰好为 0。还原的时候很简单a[k] d[1] d[2] ... d[k]也就是说原数组第 k 个数等于差分数组前 k 个位置的前缀和。你可能会问这个 d[n1] 是不是多此一举不是。差分数组的经典用途就是配合前缀和互逆而 d[n1] 就像一个“应收尾”的零头。举个例子a [1, 2, 3]那么 d[1] 1d[2] 2 - 1 1d[3] 3 - 2 1d[4] -3整体是 [1, 1, 1, -3]。你可以验证一下前三项前缀和是 1、2、3正好还原出原数组。这个哨兵位置在后面对“最终结果有几种”的分析里会变成关键角色。理解差分的一个好方法是把它想成台阶的高差。原数组就是每个台阶的海拔高度而差分数组记录的是相邻两级台阶之间差了多少。要知道第 k 级台阶的海拔就把从第一级到第 k 级的所有高差累加起来。区间整体加减这种操作在“海拔差”的视角下会变得特别直观。2.2 区间整体加减为什么只有端点受影响现在看关键映射。假设要对区间 [l, r] 整体加 1。区间里的每个数都加 1那区间内部任意两个相邻数之间的差值变了吗没变。比如 a[5] 和 a[6] 都在区间内它们同时加 1差还是原来的差。真正发生变化的只有两个地方区间左端点 l 的前一个位置a[l-1] 没动a[l] 加了 1所以 d[l] a[l] - a[l-1] 变大 1区间右端点 r 的后一个位置a[r] 加了 1a[r1] 没动所以 d[r1] a[r1] - a[r] 变小 1。于是“区间 [l, r] 加 1”在差分数组上就等价于d[l] 加 1d[r1] 减 1。反过来“区间 [l, r] 减 1”就是 d[l] 减 1d[r1] 加 1。我用前面的例子验证一遍。a [1, 2, 3]差分 d [1, 1, 1, -3]。现在操作区间 [2, 3] 减 1对应 d[2] 减 1、d[4] 加 1差分变成 [1, 0, 1, -2]。再做前缀和a[1] 1a[2] 1 0 1a[3] 1 0 1 2得到 [1, 1, 2]。这与直接对原数组操作的结果完全一致。这就是差分数组最核心的威力原数组上一个覆盖一整段的操作变成差分数组上两个位置的修改时间复杂度是 O(1)。2.3 把操作抽象成“两两配对”继续深入一步。不管是加 1 还是减 1一次操作在差分数组上的本质都是选两个位置一个加 1另一个减 1。位置的范围从 1 到 n1其中 d[1] 对应原数组第一个元素的变化d[n1] 对应最后一个元素之后的变化。这个抽象非常重要。它意味着整道题可以改写成这样我有一个长度为 n1 的整数数组 d其中 d[1] 到 d[n1] 的总和为 0每一次操作就是挑两个位置一增一减单位幅度都是 1。我要通过若干次这种配对操作让 d[2] 到 d[n] 这一整段全部变成 0。至于 d[1] 和 d[n1] 最后变成什么我暂时不关心。这个改写看起来只是换个说法但它把问题的难度直接降了一个档次因为你现在面对的已经不是区间和序列而是一组可以任意配对的“正负单元”。3. 核心思维跳跃全相等等价于差分中间归零3.1 目标的差分表述原数组 a 的所有元素相等等价于任意相邻两个元素相等也就是 a[1] a[2] ... a[n]。翻译到差分数组里就是 d[2] 0d[3] 0一直到 d[n] 0。注意这里刻意排除了 d[1] 和 d[n1]d[1] a[1]它代表的是最终那个公共值本身不要求是 0。d[n1] 只是用来收尾的哨兵它的存在是为了让差分总和为 0还原过程闭合。很多第一次接触这道题的人会在这里犯迷糊以为目标是让整个差分数组全变成 0。如果是那样原数组就会变成全 0但题目显然没要求最终值必须等于 0。我们真正要清空的只有从 d[2] 到 d[n] 这 n-1 个“中间项”。想明白这一点题目就成功了一半。我常给朋友打一个比方一排台阶你现在想让所有台阶看起来一样高。差分数组记录的是相邻台阶的高差只要所有高差都是 0台阶自然就一样高了。而第一级台阶的海拔是多少、最后一级之后是什么都只是“基准值”和“结尾标记”不影响台阶之间是否整齐。3.2 引入 pos 和 neg把凸起和凹陷分别存起来既然目标是把 d[2] 到 d[n] 全部归零那就要统计这些中间项到底有多少“正的东西”需要消掉、多少“负的东西”需要填平。定义两个变量pos所有正项之和也就是把 d[2] 到 d[n] 中所有大于 0 的数加起来neg所有负项的绝对值之和也就是把 d[2] 到 d[n] 中所有小于 0 的数取绝对值再加起来。举个例子差分数组是 [1, 0, 1, -2] 时中间项是后三项里的 d[2]0、d[3]1所以 pos 1neg 0。另一个例子差分数组 [3, -2, 1, -2]中间项是 d[2]-2、d[3]1所以 pos 1neg 2。理解这两个变量可以继续用台阶的比喻。凡是 d[i] 0说明从 a[i-1] 到 a[i] 有一个向上的“凸起”要把它削平凡是 d[i] 0说明有一个向下的“凹陷”要把它填平。pos 是所有凸起的总量neg 是所有凹陷的总量。一次操作可以理解为把一单位土从一个地方运到另一个地方。3.3 两个哨兵 d[1] 和 d[n1] 的意义为什么 d[1] 和 d[n1] 可以不被“归零”约束因为操作可以落在它们身上。特别地有一种操作是选择整个区间 [1, n] 同时加 1 或减 1它在差分数组上表现为 d[1] 和 d[n1] 一个加 1、一个减 1中间项完全不动。这个操作不改变序列的整齐度只会把最终的那个公共值整体抬高或降低。所以d[1] 和 d[n1] 本质上是一对缓冲区。如果中间的凸起或凹陷没法内部互填多出来的部分就可以被“推”到这个缓冲区里。而最终全等值 X 是多少正好对应 d[1] 最终的值。这个视角会在第 5 节讨论结果种类时派上大用场。4. 最少操作次数为什么是 max(pos, neg)4.1 一次操作最多削减多少“不平量”要证明最少操作次数先看下界。考虑一次操作对 pos 和 neg 的影响如果操作的两个位置都在 d[2] 到 d[n] 之间而且恰好是一个正项和一个负项配对那么这次操作会让 pos 减 1同时让 neg 减 1。这是最理想的情况一次操作同时解决一个凸起和一个凹陷。如果操作的一个位置在中间另一个位置是 d[1] 或 d[n1]那么这次操作只能让 pos 减 1或者只能让 neg 减 1取决于被选中的中间项是正是负。如果操作的两个位置都在哨兵 d[1] 和 d[n1] 上那么中间项完全不变这种操作对清理中间项毫无帮助最优方案里通常不会出现。于是能得出一个很强的下界每一次操作最多只能让 pos 减少 1也最多只能让 neg 减少 1。最终要把 pos 和 neg 都清零操作次数至少是 max(pos, neg)。这个推理和具体序列长什么样无关只看 pos、neg 两个总量。4.2 构造达到下界下界有了还要证明它一定能达到。假设 pos neg也就是说凸起比凹陷多。那么我的策略是先找 neg 个正项单元和 neg 个负项单元一对一配对。每一次配对正项减 1、负项加 1正好互相抵消。这 neg 次操作结束后所有负项都已经归零。剩下的 pos - neg 个正项单元已经没有负项可以和它配对了就让它和哨兵 d[1] 或 d[n1] 配对。每配对一次就是把一单位“多余的凸起”推到缓冲区里消耗一次操作。总操作次数是 neg (pos - neg) pos恰好等于 max(pos, neg)。如果 neg pos完全对称先内部配对 pos 次再把多余的负项和哨兵配对 neg - pos 次总次数是 neg。所以最少操作次数就是 max(pos, neg)。这套构造还可以用土方运输来理解凸起是要削掉的土凹陷是需要填的坑。最好的情况是凸起和凹陷直接互填一铲子解决两个问题多出来的那部分土只能运到边界外面一铲子只能解决一个问题。于是总次数等于“内部配对次数 外运次数”。4.3 用两个小例子验证结论第一个例子是 [1, 2, 3]。差分数组是 [1, 1, 1, -3]中间项是 d[2]1、d[3]1所以 pos 2neg 0。max(2, 0) 2也就是最少 2 次。前文验证过两次操作确实可以让它变成全相等的序列这里是可达的。第二个例子是 [1, 2, 1]。差分数组是 [1, 1, -1, -1]中间项是 d[2]1、d[3]-1所以 pos 1neg 1。max(1, 1) 1。手动操作一下区间 [2, 2] 减 1原数组从 [1, 2, 1] 变成 [1, 1, 1]一步到位。这也符合直觉正负刚好能内部配对时一次操作就能同时清掉一个凸起和一个凹陷。这两个例子的对照很有价值前一个例子 pos 和 neg 差得很多操作次数完全由 pos 决定后一个例子 pos 和 neg 相等内部就能自洽。正是这种差异为下一节的结果种类问题埋下了伏笔。5. “最终有几种结果”为什么是 |pos - neg| 15.1 当正负恰好相等时结果唯一先看最简单的情况pos neg。这个时候中间的所有凸起和凹陷都能内部配对一次操作同时消掉一个正项和一个负项全程不需要碰哨兵。既然 d[1] 没有被任何操作改变那么最终全等值 X 就等于最开始的 a[1]也就是 d[1] 的初始值不会有第二种可能。所以结果种类是 1。观察公式|pos - neg| 1 0 1 1完全吻合。回到台阶比喻。凸起和凹陷刚好一样多时所有的土都内部消化了第一级台阶的高度从头到尾都没动过最后所有台阶自然维持在最初第一级台阶的高度。5.2 多出来的部分让最终值开始“滑动”如果 pos 不等于 neg情况就开始有趣了。假设 pos neg那么完成最少步数操作后有 pos - neg 个正项单元是和哨兵配对的。这些配对操作有一个选择到底和左边的哨兵 d[1] 配对还是和右边的哨兵 d[n1] 配对。关键是这两种配对会造成不同的最终值偏移。如果和左边的哨兵配对相当于改变了 d[1]如果和右边的哨兵配对则不改变 d[1]。设这个“和左边配对”的次数为 x那么 x 可以从 0 取到 pos - neg每一个整数取值都对应一个不同的最终全等值。x 0 时有一种结果x 1 时偏移 1 个单位又是一种结果一直到 x pos - neg 时是最后一种结果。总共就是 pos - neg 1 种。举个具体的例子还是 [1, 2, 3]pos 2neg 0。最终结果有 2 - 0 1 3 种分别对应 x 0、1、2 三种情况。手动验证一下x 0 时全等值为 1x 2 时全等值为 3x 1 时全等值为 2三种都能在两步内达到。这就是为什么 |pos - neg| 决定种类数它量化了“多余出来的缓冲量”而哨兵配对时选择左还是右让最终值发生连续滑动。如果 neg pos推理完全对称只是多出来的负项让最终值往另一个方向滑动种类数仍然是 |pos - neg| 1。所以不管哪边多公式都统一写成 |pos - neg| 1。5.3 最容易栽的坑不限制最少步数时结果是无限种这里我必须专门停下来提醒一个容易踩的坑。如果不把“最少操作次数”这个前提写清楚这道题的最终结果种类其实是无限多的。为什么假如你用一种方案让序列变成了全相等的 X接下来可以对整个区间 [1, n] 再执行一次加 1序列全体变成 X1依然全相等。再做一次变成 X2。同理也可以减 1、减 2……所以只要允许任意次操作最终值可以从负无穷一路取到正无穷。很多初学者在这个地方绕不出来就是因为忽略了题面里的“最少操作次数”限定。一旦限定了步数必须是最小值就没有多余的步数让你去整体平移了最终值的范围才会被 |pos - neg| 1 锁死。所以在做题前先确认题意如果题面没有明确写“最少操作次数下”那这个公式对应的其实是另一个更隐蔽的问题在方案可以达到最少步数的前提下能产生多少种不同的最终结果。6. 代码落地边界、溢出和输入格式6.1 Python 完整代码先给一个可直接运行的 Python 版本。输入格式我按常见的“第一行是 n第二行是 n 个数”处理import sys def main(): data list(map(int, sys.stdin.read().split())) if not data: return n data[0] a [0] data[1:1 n] # 构造差分数组长度 n 2下标 1 到 n 1 d [0] * (n 2) d[1] a[1] for i in range(2, n 1): d[i] a[i] - a[i - 1] d[n 1] -a[n] # 统计中间项的正盈余和负欠账 pos 0 neg 0 for i in range(2, n 1): if d[i] 0: pos d[i] else: neg - d[i] # 因为 d[i] 是负数减它等于加绝对值 print(max(pos, neg)) print(abs(pos - neg) 1) if __name__ __main__: main()代码本身很短核心就三步构造差分、统计正负、输出结论。需要注意neg - d[i]这个写法因为 d[i] 是负数减一个负数等价于加绝对值。如果你更喜欢可读性强的写法也可以写成neg -d[i]效果一样。6.2 C 版本与 long longC 版本需要特别注意数据类型。pos 和 neg 是中间项绝对值之和在最坏情况下n 可以到十万每个数的绝对值可以到 1e9累加出来的和会达到 1e14 这个量级远超 int 的范围必须用 long long。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long a(n 2), d(n 3); for (int i 1; i n; i) cin a[i]; d[1] a[1]; for (int i 2; i n; i) { d[i] a[i] - a[i - 1]; } d[n 1] -a[n]; long long pos 0, neg 0; for (int i 2; i n; i) { if (d[i] 0) pos d[i]; else neg - d[i]; } cout max(pos, neg) \n; cout (pos neg ? pos - neg : neg - pos) 1 \n; return 0; }这里我刻意避免了直接对 long long 用 abs因为不同编译环境下 abs 的重载行为容易造成困惑。直接写一个三元表达式来取绝对值又清楚又安全。6.3 必须留心的三个坑第一个坑是 n 1。序列只有一个数时它本来就全相等差分数组中间项是空的pos 和 neg 都是 0答案分别是 0 和 1。代码里循环for i in range(2, n 1)天然不会执行输出会正确。但如果是自己写死判断或手动初始化很容易在这里翻车。第二个坑是数组长度和下标。差分数组需要用到 d[n1]所以数组至少要开 n 2 个位置。C 里vector开 n 2 或 n 3 都行但不要手滑开成 n 1否则访问 d[n1] 就越界了。第三个坑是类型溢出。刚才已经强调过pos 和 neg 的最大值不是 n 也不是原数组某个数的范围而是 n 乘以单个数数量级之后的和。用 int 保存会导致错误结果这种问题在在线评测里非常隐蔽因为小数据怎么测都对大数据直接爆掉。6.4 自测用例表我整理了几个适合自测的输入方便你验证自己的代码输入序列中间差分项posneg最少操作次数结果种类[1]空0001[1, 2, 3][1, 1]2023[1, 2, 1][1, -1]1111[3, 1, 2][-2, 1]1222其中 [3, 1, 2] 可以手动验一遍差分数组是 [3, -2, 1, -2]中间项是 -2 和 1pos 1neg 2所以最少 2 次最终结果 2 种。试试先操作区间 [1, 1] 减 1得到 [2, 1, 2]再操作区间 [2, 2] 加 1得到 [2, 2, 2]。这是其中一种。另一种最终值可以通过不同的哨兵配对方式得到正好对上种类数 2。7. 这道题真正想训练你的东西7.1 从“改数值”到“改差异”的思维迁移这道题看起来是在考差分数组模板实际上考的是算法思维里一个非常核心的能力识别不变量。区间整体加减区间内部的“相对差异”是不变量变化的只有边界。把视角从每个数本身切换到相邻数的差值上问题复杂度直接从 O(n) 降到 O(1)所有后续推导都建立在这一点上。这种“找不变量、压缩变化点”的思路在计算机思维里到处都有应用。缓存系统只记录失效的条目而不是重建全部内容版本管理只存储差异而不是每次存整个快照本质上都是同一套思考方式。7.2 差分数组的扩散应用如果你把这道题的差分思想吃透了后续会遇到一串同门兄弟。区间加是差分的直接应用维护一个差分数组区间加完后做一次前缀和还原就能高效求出每个位置的最终值。树上差分处理路径上的批量修改二维差分处理矩形区域的批量加值它们的核心逻辑都和这里一模一样把区间操作转换成边界点的修改最后统一做前缀和。7.3 我的二刷建议我个人刷这道题的顺序是这样第一遍看题解背住了 max(pos, neg) 和 |pos - neg| 1但总觉得是空中楼阁第二遍自己动手证了一遍下界和构造才算真正理解为什么操作次数等于这两个数的较大者第三遍专门去验证“最终结果种类”这个反直觉的结论手动枚举了 [1, 2, 3] 的所有两步方案才彻底弄懂哨兵配对的滑动机制。所以我建议你拿到题之后先别急着抄代码把第 4 节和第 5 节的两个结论各推导一遍再写代码。写完之后一定把 n 1 的边界和哨兵位置都测一遍这样才算真正消化了题目。尤其是“最终结果种类”这一问很多题解直接给公式却不解释为什么你亲手推一次之后以后再遇到类似的差分问题会少走很多弯路。