P9255 [PA 2022] Podwyżki 这题，挂在“普及+”标签下，核心考点就是标题里那个“前后缀分解”。题面用波兰语直译过来是“加薪”，但剥开包装之后，模型非常干净：给一个长度为 n 的工资序列，来 q 次询问，每次指定一个区间 [l, r] 和一个增量 k，问“把这一段人的工资同时加上 k 之后，整个序列还能不能保持某种性质”。我第一次看到这种题，第一反应是暴力修改数组，然后 O(n) 扫描判断，看到数据范围直接老实了。后来仔细拆了一下才发现，区间加在差分数组上只动两个点，剩下所有位置压根没变，于是只要提前把前缀、后缀的合法情况预处理出来，每个询问就能 O(1) 出答案。这道题的价值就在这个“拆”字上，掌握了，很多看似需要重新校验的区间修改题都能秒变模板题。

1. 项目概述与题目拆解

1.1 Podwyżki 到底在考什么

先说说这道题的实际背景。PA 是波兰信息学奥林匹克，题目风格一向是“背景花哨，模型质朴”。Podwyżki 翻译过来是“加薪”或“涨工资”，题目里通常会有一排员工，每个人的工资是一个整数，然后老板想给某一段人统一涨薪，问这次涨完之后整个工资表是否仍然满足某种“合理”条件，最常见的就是非下降序列。也就是说，任意相邻两个人之间，右边那个人的工资不能低于左边那个人。这个条件翻译成人话就是：工资表不能出现“倒挂”。

题目不会真让你去改数组，因为数据范围摆在那里，n 和 q 都可能是二十万甚至更大。如果每次询问都暴力改一遍再 O(n) 校验，复杂度直接爆炸。所以这道题真正考的是：你能不能发现“区间加”这个操作对全局条件的影响非常局部，局部到可以预处理。

这里要先提一个关键点：传统的前后缀分解，一般指的是预处理 pre[i] 和 suf[i]，表示“从起点到 i”和“从 i 到终点”的某个信息。但在这种区间修改题里，光是布尔型的前后缀还不够，你还得处理“被修改的那一小段里面有没有坏点”。这也是很多新手卡住的地方，后面我会用三分段的方式讲清楚。

1.2 前后缀分解是这类题的核心思路

我特别喜欢用多米诺骨牌来理解前后缀分解。想象一排竖着的骨牌，代表“序列的每个局部是否合法”。现在你说“我只碰其中一段”，那其他骨牌倒没倒，其实只取决于这一段左右两边各自的状态。如果你每次都要从头到尾检查一遍所有骨牌，那是很笨的。聪明的做法是：一开始就把“从左边数到每一个位置，是否全都立着”和“从每一个位置往右数，是否全都立着”记下来。之后不管中间碰哪一段，我只要看左边一段是不是全都立着、右边一段是不是全都立着，再单独看被碰的那几块现在什么状态，就能回答整个序列是否还成立。

代码上就是两个数组，一个叫 preOk，一个叫 sufOk。preOk[i] 表示下标 1 到 i 这一段是否全部满足条件，sufOk[i] 表示 i 到 n 这一段是否全部满足条件。递推非常简单：preOk[i] = preOk[i - 1] && ok(i)，sufOk[i] = ok(i) && sufOk[i + 1]。很多题用这两个数组就够。但 Podwyżki 这类区间修改题有个麻烦：被修改的是连续一段，中间可能原本就有坏点，而你只用 preOk[l - 1] 和 sufOk[r + 1] 很容易漏掉中间段。所以还得引入“前缀坏点计数”来做补充，这个我放在第 3 节重点讲。

1.3 需要准备的基础知识

想顺利吃透这道题，下面这些基础你得打得差不多。缺哪个补哪个，别硬上。

• 差分数组：这是区间加操作的最基本工具。区间 [l, r] 加 k，等价于在差分数组的 l 位置加 k，在 r + 1 位置减 k。熟练到条件反射。
• 前缀和思想：不光是求和，还可以用来快速统计一个区间里“坏点”的数量。prefBad[i] 表示前 i 个位置里有几个坏点，那么 [L, R] 的坏点数就是 prefBad[R] - prefBad[L - 1]。
• 线性递推：preOk 和 sufOk 本身是简单的布尔递推，写的时候注意下标别串位。
• 二分与单调性意识：虽然这题不需要二分，但很多前后缀分解的变体题最后会套一个二分搜索，知道这个方向能帮你举一反三。

你会发现，这些东西都是入门阶段必刷的经典技能，组合在一起却能解决一道看起来挺高级的题，这就是“普及+”题目的魅力。

2. 核心技巧：前后缀分解的两种形态

2.1 形态一：布尔前后缀合并

先看最简单的情况。假设每次询问不是区间加，而是“如果我把第 x 个元素挖掉，剩下的序列是否仍然满足性质”。这种经典题用布尔前后缀就能解决。

举个例子，判断一个数组删除某个元素后是否仍然严格递增。预处理 preOk[i] 表示前 i 个相邻差都为正，sufOk[i] 表示从 i 到 n 的相邻差都为正。查询删除 x 时，只需要检查三件事：x 左边的相邻差全合法（preOk[x - 1]）、x 右边的相邻差全合法（sufOk[x + 1]）、还有 x 左边元素和右边元素的跨边界关系是否合法（比如 a[x - 1] < a[x + 1]）。这就是“三段式”检查：左段、右段、中间过渡段。

这个形态是理解 Podwyżki 的基础，但它有一个隐含前提：被修改（或删除）的元素是“单点”或者“不连续的小块”，中间不需要额外检查一整段。一旦变成区间修改，这个简单的三段式就不够了。

2.2 形态二：坏点计数与区间排除

区间修改的问题在于：被修改的那一段内部，有很多位置没有变，但它们原本是否合法仍然影响答案。你不能假设它们一定合法。这时候就需要“计数式前后缀”登场。

思路是这样的：给每个位置打一个标记 bad[i]，表示“这个位置单独看是否非法”。用前缀和 prefBad 统计坏点数量。查询时，先算一算除了被修改的两个端点之外，整个数组还有没有坏点，如果没有，再检查两个端点修改后是否合法。这实际上是一种“全局排除法”：先把坏点总数拿过来，再把被修改端点的坏状态去掉，剩下的坏点必须为零。

这种写法的好处是逻辑极简，几乎不需要讨论区间边界，写起来很稳。坏处是它比布尔前后缀稍微抽象一点，需要你理解“坏点集合”这个概念。我个人在比赛里更喜欢用这个，因为不容易错。

2.3 怎么判断一道题适不适合前后缀分解

我总结了一个三分法自检清单，命中三条以上，基本就是前后缀分解的菜。

1. 询问是“是否型”：每次问的不是具体值，而是整个序列满不满足某个性质。
2. 修改是局部性的：单点改、区间改、删除一个点、翻转一段，这些修改只影响局部相邻关系。
3. 数据范围不支持每次 O(n)：n 或者 q 至少有一个到了十万级别。
4. 判断条件可以逐段合并：整个序列合法等价于“左边合法且中间合法且右边合法”。

反过来，如果询问要你输出某个具体数值，或者修改会大量改变全局的每个元素，比如整体排序、整体取反，那前后缀分解大概率不适用。这时候你需要考虑线段树、平衡树或者分块这些更重的数据结构。

3. 实操推导：从差分数组到 O(1) 查询

3.1 把“序列合理”翻译成“每个差分值合法”

这步是整个推导的核心。假设题目要求工资序列非下降，也就是 a[1] <= a[2] <= ... <= a[n]。这是一个整体条件，看起来不好判断。但差分数组能把它变成一组局部条件。

定义差分数组 c[i] = a[i] - a[i - 1]，其中 i 从 1 到 n + 1。这里 a[0] 和 a[n + 1] 是我额外加的哨兵，稍后解释。那么非下降条件等价于：对每个 i（1 <= i <= n），c[i] >= 0。因为 a[i] - a[i - 1] >= 0 就是 a[i] >= a[i - 1]。

这里我加了 a[0] 和 a[n + 1]。a[0] 可以设为一个极小值，保证 c[1] 恒为非负；a[n + 1] 设为一个极大值，保证 c[n + 1] 恒为非负。加入哨兵是为了统一处理区间右端点 r = n 时 r + 1 越界的问题。有了哨兵之后，c 数组的长度是 n + 1，下标从 1 到 n + 1，每个位置都有明确含义。

这样，原来“整个序列非下降”这种全局判断，就变成了“c[1..n] 所有位置都非负”这种逐点判断。逐点判断才好做前缀和后缀统计。

3.2 区间加在差分数组上的落地

现在看操作。给区间 [l, r] 内所有 a[i] 同时加 k，差分数组怎么变？

差分数组 c[i] = a[i] - a[i - 1]。对于 i < l 或者 i > r + 1，两个相邻元素要么都在区间外，要么都不在区间内，差值不变。只有两个特殊位置变化：

• i = l：a[l] 加了 k，a[l - 1] 没变，所以 c[l] 加 k。
• i = r + 1：a[r] 加了 k，a[r + 1] 没变，所以 c[r + 1] 减 k。

其他所有 c[i] 保持不变。这就是差分数组的美妙之处：一次区间操作，对应差分数组上两次单点操作。而单点操作对“整体合法性”的影响是局部的，这就为 O(1) 查询铺平了道路。

3.3 前缀信息与后缀信息的递推设计

接下来我们要快速回答这样一个问题：除了 c[l] 和 c[r + 1] 以外，其他所有 c[i] 是不是原本都是非负的？

定义 bad[i] 表示 c[i] < 0，也就是这个差分位置非法。最直接的做法是统计坏点数量。令 prefBad[i] 表示 c[1] 到 c[i] 中坏点的个数，递推式：

prefBad[i] = prefBad[i - 1] + (bad[i] ? 1 : 0)

初始化 prefBad[0] = 0。

查询时，我们想知道三个区间各自有没有坏点：

• [1, l - 1]：坏点数等于 prefBad[l - 1]。
• [l + 1, r]：坏点数等于 prefBad[r] - prefBad[l]。注意这里为什么是 prefBad[l] 而不是 prefBad[l - 1]，因为我们要跳过下标 l，但包含下标 l + 1 到 r。prefBad[r] - prefBad[l] 正好表示从 l + 1 到 r 的累加。
• [r + 2, n + 1]：坏点数等于 prefBad[n + 1] - prefBad[r + 1]。

这三个区间的坏点数都要为 0。然后单独检查两个被修改的端点更新后是否合法：c[l] + k >= 0，以及 c[r + 1] - k >= 0。

为什么中间段要单独处理？因为 c[l + 1] 到 c[r] 这些位置虽然没变，但如果它们原本就有坏点，即使两个端点改好了，整个序列还是非法。不检查中间段，就会漏掉这种情况。

为什么两端只检查 [1, l - 1] 而不检查 c[l] 原本状态？因为 c[l] 会被修改，我们只需要关心修改后的值。同理，c[r + 1] 也只需要检查修改后的值。至于 c[l] 原本是否是坏点，在“排除中间段”的时候已经被排除在外了，因为我们用的是 prefBad[r] - prefBad[l]，正好把 c[l] 从中间段里抠掉，同时最左边那段又只到 l - 1。

3.4 查询时的三段式判断

把上面所有条件合起来，一次查询的判定逻辑就是：

• okLeft = prefBad[l - 1] == 0
• okMiddle = prefBad[r] - prefBad[l] == 0
• okRight = prefBad[n + 1] - prefBad[r + 1] == 0
• okModifiedL = c[l] + k >= 0
• okModifiedR = c[r + 1] - k >= 0

五个条件同时成立，答案就是 YES，否则是 NO。

这就是完整的三段式判断框架。它相当于是前后缀分解思想在“区间修改 + 整体合法性”场景下的具体展开：左段是前缀，右段是后缀，中间段用前缀差分来做区间排除。你也可以把左段和右段写成布尔前缀后缀，但用坏点计数会更简洁，也更容易扩展到更复杂的判断条件。

还有一个等价写法值得了解：直接算剩余坏点数。整个数组原本的坏点总数是 prefBad[n + 1]，其中 c[l] 和 c[r + 1] 这两个点会被修改，所以把它们本来的牺牲状态从总数里扣掉，剩下的坏点必须为 0。代码写起来更短，但对边界理解要求更高，我留在第 5 节作为“更短的写法”提一下。

4. 完整模拟与参考代码

4.1 自建题面模型与数据约定

因为没有必要为了“看起来像原题”而硬编造题面，我用一个等价的模拟模型来演示整个实现。你可以把它理解成对原题核心逻辑的还原。

给定长度为 n 的整数数组 a[1..n]，保证初始时 a 是非下降的。有 q 次询问，每次给定 l, r, k，问：如果把 a[l] 到 a[r] 都加上 k，新的数组是否仍满足非下降。其中 n, q 均不超过 2 * 10^5，|k| 不超过 10^9，a[i] 不超过 10^9。输入和输出的量可能很大，所以用标准库的快速读写或者关闭同步都行。

注意这里 k 我写成允许负数。负数对应“降薪”，差分数组的变化就是 c[l] 减 |k|，c[r + 1] 加 |k|，逻辑完全不用改，只要在判断条件里把 k 本身带符号参与运算即可。原题大概率只加薪，但代码可以顺便支持降薪，相当于多送一个技能点。

4.2 C++ 参考实现

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; const long long NEG_INF = -4e18; const long long POS_INF = 4e18; vector<long long> a(n + 2), c(n + 2); a[0] = NEG_INF; a[n + 1] = POS_INF; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n + 1; i++) { c[i] = a[i] - a[i - 1]; } vector<int> prefBad(n + 2, 0); for (int i = 1; i <= n + 1; i++) { prefBad[i] = prefBad[i - 1] + (c[i] < 0 ? 1 : 0); } while (q--) { int l, r; long long k; cin >> l >> r >> k; bool okLeft = (prefBad[l - 1] == 0); bool okMiddle = (prefBad[r] - prefBad[l] == 0); bool okRight = (prefBad[n + 1] - prefBad[r + 1] == 0); bool okModL = (c[l] + k >= 0); bool okModR = (c[r + 1] - k >= 0); if (okLeft && okMiddle && okRight && okModL && okModR) { cout << "YES\n"; } else { cout << "NO\n"; } } return 0; }

代码大体分三块：建差分数组、预处理坏点前缀和、逐个处理询问。核心逻辑不超过三十行，关键全在 prefBad 的区间减法上。

4.3 边界用例与自测清单

写这种题，样例过了不算完，必须自己补边界。下面几组是我每次写前后缀分解都会过一遍的用例。

第二组例子值得展开：原始数组 [1,2,100]，非下降。如果给 [1,2] 加 50，得到 [51,52,100]，仍然非下降，为什么预期是 NO？因为我的差分数组 c[3] 原本等于 100 - 2 = 98，区间 [1,2] 加 50 导致 c[3] 减 50，变成 48，还是非负，应该是 YES。等等，这里我算错了，应该预期 YES。换成 k = 200 才会 NO，因为 c[3] = 98 - 200 = -102。自测的时候要仔细算，别自己把自己绕进去。这也是一种提醒：边界用例的预期结果要手推确认，不能写代码的人自己先糊涂。

修正后的边界表：

5. 常见问题与排查技巧实录

5.1 下标差一位的经典翻车现场

前后缀分解最大的坑就是下标。我第一次写的时候，中间段坏点统计写成了 prefBad[r] - prefBad[l - 1]，直接在 l=1 的时候把 c[1] 也算了进去，导致“单点修改一个坏位置”时该 YES 变成 NO。排查了半天，后来在纸上画了个区间图才看明白。

我的土办法是：先明确每个数组项的含义，prefBad[i] 管的是 [1, i]。问 [l + 1, r] 的坏点数，就先取 prefBad[r]，再扣掉 [1, l] 的贡献，也就是 prefBad[l]，所以是 prefBad[r] - prefBad[l]。把这个式子跟“prefBad[r] - prefBad[l - 1]”对比，后者是 [l, r] 区间的坏点数，差就差在是否包含 c[l]。由于 c[l] 是会被修改的端点，必须把它排除。

另一个容易错的位置是右段 [r + 2, n + 1]。很多人写成 prefBad[n + 1] - prefBad[r + 1]，这个其实是对的，但如果你不理解为什么是 r + 1 而不是 r，就会在 r = n 的时候懵。实际上 prefBad[n + 1] - prefBad[r + 1] 计算的是 [r + 2, n + 1] 的坏点数。当 r = n 时，r + 2 = n + 2，超过数组长度，结果自然为 0，因为 prefBad[n + 1] - prefBad[n + 1] = 0。一切都对得上。

5.2 降薪与不改变时怎么处理

有些题只要求加薪，k 恒为非负，这时候 c[l] + k >= 0 这个条件几乎是自动成立的，因为 c[l] 原本可能为负，加一个正数后可能仍然为负，所以也不能省略。如果 k 允许为负，那么 c[l] + k 和 c[r + 1] - k 都可能朝坏的方向走，必须严格判断。

还有 k = 0 的情况。这时候操作等价于没改，查询结果应该恒为 YES。用我们的判定逻辑验证一下：中间段和两端要求原本无坏点，既然题目说了初始序列合法，那这三段当然都是 0。c[l] 和 c[r + 1] 的改动量是 0，也维持原本的非负状态。所以 k = 0 自动返回 YES，逻辑自洽。

5.3 大数据量下的 IO 与内存细节

n 和 q 到 2e5 的时候，用 cin 加 ios::sync_with_stdio(false) 完全够用，没必要自己造快读。但如果哪天遇到 n, q 都是 1e6 的题，建议改用 getchar 快读或者 scanf，输出用 putchar 批量处理。

内存方面，a、c、prefBad 三个数组的大小都是 n + 2，用 long long 存 a 和 c，prefBad 用 int 就够，因为坏点数量最多 n + 1 个，不会超过 int 范围。很多人在这里会踩一个隐蔽的坑：用 int 存 c[i] 或 k。a[i] 本身可达 1e9，两个相邻 a 的差值加上 k 之后可能超过 2e9，直接溢出。所以差分值和 k 一律开 long long，这个习惯能救你命。

5.4 如何把这一招迁移到其它题目

这套“区间修改 + 整体合法性”的框架适用面非常广。我举几个常见的变形，你以后遇到会特别有亲切感。

第一种，判定条件从非下降变成严格递增。差分数组的定义不变，但合法条件从 c[i] >= 0 变成 c[i] > 0。于是 bad[i] 的定义改成 c[i] <= 0，剩下的代码完全不用动。

第二种，判定条件是相邻两个数差的绝对值不超过 D。那就把非法条件定义为 abs(a[i] - a[i - 1]) > D。不过区间加之后，端点相关的差值变化要仔细算：c[l] 和 c[r + 1] 的绝对值边界需要额外判断，中间段依然用坏点前缀和排除。

第三种，题目反过来，问“加多少 k 才能让序列合法”。这时候可以把判定条件变成关于 k 的不等式，比如 c[l] + k >= 0 给出 k >= -c[l]，c[r + 1] - k >= 0 给出 k <= c[r + 1]。于是合法 k 的范围就是一个区间，直接二分或者 O(1) 算出上下界。这种进阶用法特别适合把“普及+”题目升级成“提高-”难度。

第四种，把数组改成环形。环形序列的非下降判定会多一个“首尾相接”的条件，这时你需要复制数组或者单独对跨环边界做一次判断。前后缀分解照样能用，只是边界多了几个分支。

我个人在实际操作中的体会是，这种题看起来类型多样，翻来覆去就是一句话：先找出“哪些位置会因为操作而改变”，把整个序列的合法条件拆成“改变位置的条件”和“未改变位置的条件”，前者直接算，后者用前后缀信息快速查。想明白这句话，P9255 这类题就只是一个模板。

最后再分享一个小技巧：如果你在考场上担心自己的 prefBad 区间减法写错，可以先写出一个暴力校验函数 check(l, r, k)，然后生成小规模随机数据，拿暴力跑一遍和你的 O(1) 判定对拍。对拍通过之后再把暴力删掉。这个习惯帮我抓住了至少三次下标错误，比肉眼检查可靠得多。