10215 字

51 分钟

【ACM 算法随笔】差分数组与差分思想

2025-11-25

ACM Note

Algorithm

/

Trick

/

Note

/

ACM

差分数组基本原理#

差分是一种 常用且高效 的数组处理技巧，其核心在于将 原本作用在整个区间上的线性更新 ，巧妙地转化成 区间端点的局部常数级操作 。在处理带有频繁区间修改的问题时，直接维护原数组往往会造成 $O(nq)$ 的高额开销，而差分数组通过记录 相邻元素之间的变化 ，替代了原本的线性更新。我们定义差分数组：

d[i] = a[i] - a[i-1]

这意味着原数组中的每一个元素都可以通过对差分数组 求前缀和 恢复出来。差分的关键优势在于，它允许我们在 仅修改两个位置 的前提下完成对 整个区间 的批量更新。例如，若需将区间 $[l, r]$ 内的所有元素同步增加 $x$ ，在差分数组中仅需执行 d[l] += x 以标记变化的开始，并在 d[r+1] -= x 处标记变化的结束。

这种机制将单次区间更新的时间复杂度从线性的 $O(n)$ 直接降至常数级的 $O(1)$ 。在算法设计中，差分不仅是批量区间修改问题的利器，更是构造前缀和结构、处理扫描线类问题的底层逻辑，是一种将全局更新转化为局部增量的简洁而高效的基础技巧。

差分的狭义视角#

从数学本质上看，差分可以被视为 离散意义下的导数 。在连续数学中，导数刻画的是函数在瞬时状态下的变化率；而在离散的计算逻辑中，由于无法进行极限运算，我们便利用相邻差来描述序列的变化趋势：

d[i] = a[i] - a[i-1]

这一映射关系完美对应了连续函数中倒数的近似关系：

f'(x) \approx f(x) - f(x-1)

在这种视角下，原数组描述的是系统的状态 ，而 差分数组描述的是状态的变化 。对差分数组求前缀和的过程，本质上等同于对离散导数 进行一次积分 ，从而由变化率还原出原函数的状态轨迹。

这种思路的强大之处在于，它让我们不再盯着最终的数组结果看，而是先去处理每一次操作带来的增量。不管是频繁修改一段区间的值，还是统计多个重叠区域的覆盖情况，核心逻辑都是一致的：先把所有的变化量记录在差分数组里，最后再通过一次前缀和扫描还原出全局的结果 。这种化繁为简的策略，不仅大幅降低了重复计算的开销，也构成了处理区间类问题最基础、最实用的思维模板。

具体思路可以看 N 神的视频讲解

差分的广义视角#

在很多算法问题中，我们经常会遇到一种情况：题目所要求的条件本身并不方便直接计算，但如果稍微改变一下 统计的方式或表达的形式 ，问题就会立刻变得容易处理。这类通过 改变统计对象或约束表达 来化简问题的思路，可以从更宽泛的角度理解为一种 广义的差分思想 。它并不局限于数组中的相邻元素之差，而是更强调通过 构造两个更容易计算的量，再通过差分得到目标结果 ，从而规避直接处理复杂条件的困难。

在这种思路下，我们往往不会直接去求目标答案，而是先寻找一些 更容易计算的辅助函数或统计量 。当问题被重新表达之后，原本精确而复杂的条件有时可以被替换为 更宽松、更单调的限制 ，或者被改写成 更容易维护的结构 。最终再通过简单的相减或差分操作，就能够恢复出原问题的答案。这样的转化本质上是一种 “先放宽条件、再通过差分恢复精确结果” 的过程。

在很多经典算法模型中，都可以看到这种思想的影子。例如，有时我们会把 恰好满足某个条件的计数 转化为两个 不超过某个上界的计数函数之差；有时会把 区间上的信息 改写为 前缀形式 来进行计算；还有一些原本需要同时考虑 上下边界的范围条件 的问题，也可以通过差分转化为 只需要处理单侧限制 的形式。虽然这些技巧在表面上属于不同的知识点，但如果从更抽象的角度来看，它们都体现了同一种核心思路：通过改变问题的表达方式，使答案可以由两个更简单的问题之差得到 。

差分构造题目收集#

在处理区间增减操作时，直接观察原数组往往会陷入 全局耦合的困局 。由于区间操作在空间上存在高度重叠，每个位置的最终数值均是多次操作叠加的结果，这种复杂的相互作用使得 操作顺序的梳理与方案的构造 极具挑战。然而，此类问题的本质并非数组的绝对数值，而是 相邻位置间变化量的生成机制 。通过引入差分序列 $d_i = a_i - a_{i-1}$ ，我们可以将原本全局性的区间覆盖精确地转化为 局部性的端点变动 ，对区间 $[l, r]$ 的整体操作，在差分域中仅表现为 $d_l$ 与 $d_{r+1}$ 两个孤立点的数值修正。

当视角切换至差分域后，关于原数组的构造问题便精确地转化为：是否存在一组满足特定约束的差分序列，使其通过前缀和还原后能与目标数组精确对齐 。在这种逻辑框架下，棘手的区间干涉消失了，取而代之的是对差分序列取值范围、正负分布以及代数守恒关系的分析。大多数题目最终都会转化为对差分序列总和的校验，或者是对端点数值抵消的匹配构造。

从算法特性的角度审视，差分数组的核心优势在于其 静态验证的高效性 。差分技巧常用于多修改、单查询的场景，而构造类题目恰好契合这一特性，其核心诉求往往是在执行完一系列潜在操作后，进行 仅有一次的最终验证或方案输出 。这种一次性查询的本质，使得差分法成为了处理此类构造问题的最优解，它有效规避了复杂的动态维护，将深奥的构造逻辑压缩至有限的时间复杂度之内。

构造所需的数组#

题目链接

Problem Statement#

给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的大小，且一开始全部为 $0$ 。一次操作中，你可以从 initial 数组中选择任何子数组，并将每个值加 $1$ 。

返回从 initial 数组构造 target 数组的最少操作次数。答案保证在 $32$ 位整数以内。

Constraints#

$1 \leq target.length \leq 10^5$
$1 \leq target[i] \leq 10^5$

Input#

输入包含两行：

第一行包含一个整数 $N$ ，其中 $N$ 表示数组的长度。
第二行包含 $N$ 个整数，表示数组中的元素。

$N$

$target_1 \quad target_2 \quad \ldots \quad target_N$

Output#

输出一个整数表示答案。

Sample Input 1#

5
1 2 3 2 1

Sample Output 1#

Sample Input 2#

4
3 1 1 2

Sample Output 2#

题目要点解析#

这道题的操作是每次可以选择一个子数组 $[l, r]$ ，并将其中所有元素同时加 $1$ 。初始数组全部为 $0$ ，目标是构造出数组 target 。如果直接从区间修改的角度思考会比较复杂，因此可以通过 差分数组 来观察数组中数值的具体变化。定义差分数组：

diff_i = target_i - target_{i-1}

差分数组反映的是数组在相邻位置之间的变化量，也就是数值发生改变的变化点。如果 diff_i > 0 ，说明在位置 $i$ 出现了上升；如果 diff_i < 0 ，说明在位置 $i$ 出现了下降。进一步考虑一次区间操作 $[l, r]$ 对差分数组的影响。区间加 $1$ 在差分数组中等价于在位置 l 增加 +1 ，在位置 r + 1 增加 -1 。

因此，每一次操作一定会产生 一个正变化点和一个负变化点 ，因此在最终的差分数组中，一个正数变化点对应一个负数变化点。如果某一侧的数量更多，就说明有一部分变化点实际上落在数组边界之外。如果 正数变化量更多 ，说明有一部分负变化点落在数组右侧越界的位置；反之，如果 负数变化量更多 ，则说明有一部分正变化点在数组左侧越界的位置。

因此，只需要统计差分数组中的正/负数变化量之和：

P = \sum_{i=1}^{n} \max(0, diff_i) \quad N = \sum_{i=1}^{n} \max(0, -diff_i)

由于这些变化点需要相互配对才能形成一次完整的区间操作，因此最少操作次数就是两者中的较大值。整个过程只需要遍历一次数组并计算差分即可完成统计，因此时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$ 。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main(){
5

6
}

使数列递增所需的最少操作次数#

题目链接

Problem Statement#

给定一个长度为 $n$ 的整数序列 $A = (A_1, A_2, \ldots, A_n)$ ，以及 $m$ 个整数区间 $(L_i, R_i)$ 。你可以对序列 $A$ 进行任意次数的以下操作：选择一个整数 $i$ （ $1 \leq i \leq m$ ），将 $A_{L_i}, A_{L_i+1}, \ldots, A_{R_i}$ 的每一个元素加 $1$ 。

请判断是否能将 $A$ 变为广义单调递增序列。若可以，求出最少需要的操作次数；若无法做到，请输出 $-1$ 。

Constraints#

$1 \leq n \leq 300$
$1 \leq m \leq 300$
$1 \leq A_i \leq 300$
$1 \leq L_i \leq R_i \leq n$
所有输入均为整数

Input#

输入包含多行：

第一行包含两个整数 $n$ 和 $m$ 。
第二行包含 $n$ 个整数，依次表示序列 $A_1, A_2, \dots, A_n$ 。
接下来 $m$ 行，每行包含两个整数 $L_i, R_i$ ，表示第 $i$ 个区间的左右边界。

$n \quad m$

$A_1 \quad A_2 \quad \ldots \quad A_n$

$L_1 \quad R_1$

$\ldots$

$L_m \quad R_m$

Output#

输出一个整数，表示最少操作次数，若无法完成则输出 -1 。

Sample Input 1#

Sample Output 1#

Sample Input 2#

Sample Output 2#

-1

Sample Input 3#

Sample Output 3#

题目要点解析#

在离散的角度下看，差分数组相当于原数组的导数，因此要想让原数组单调递增，只需要让差分数组的所有元素都大于 $0$ 即可。在差分的视角下，原题中的区间加操作，本质就是将 $L_i$ 位置的数值 $+1$ ，将 $R_i + 1$ 位置的数值 $-1$ 。也就是说，每次操作相当于将 $R_i + 1$ 位置的物品分出一份给 $L_i$ 位置，并付出 $1$ 的操作代价。

于是这道题就可以转化为：在若干个给定的调配通道下，能否通过最少次数的调度，将每个位置的差分值都调整到大于等于 $0$ 。这种带有运力限制与最优化代价的全局调配问题，可以转化为最小费用最大流解决。

我们建立一个包含超级源点 $S$ 、超级汇点 $T$ 以及各个差分位置结点的网络拓扑。对于差分初始状态，根据各位置物资的盈缺情况进行分类连边：

对于 $d_i > 0$ 的位置，说明该处物资富余，我们从源点 $S$ 向该位置引一条流量为 $d_i$ 且费用为 $0$ 的边

\text{Capacity}(S \to i) = d_i \quad \text{Cost}(S \to i) = 0

对于 $d_i < 0$ 的位置，说明该处物资紧缺，我们从该位置向汇点 $T$ 引一条流量为 $-d_i$ 且费用为 $0$ 的边

\text{Capacity}(i \to T) = -d_i \quad \text{Cost}(i \to T) = 0

由于原数组最后一个位置之后的差分值不需要强制大于等于 $0$ ，因此该位置相当于一个无限的物资蓄水池。我们从源点 $S$ 向该位置引一条流量为 $\infty$ 且费用为 $0$ 的边。

最后，题目中给出的 $m$ 个可选区间操作，本质上就是网络中可以利用的传送通道。对于每个区间，允许将物资从 $R_i$ 无限制地运送回 $L_i - 1$ ，且每运送单位物资需要消耗 $1$ 的代价。因此，在图中建立对应的操作边：

\text{Capacity}(R_i \to L_i - 1) = \infty \quad \text{Cost}(R_i \to L_i - 1) = 1

在具体求解时，利用最大流判断可行性、最小费用计算代价的核心思想。首先统计出全网的总缺口：

K = \sum_{i} \max(-d_i, 0)

由于通往汇点 $T$ 的每条管道都受限于该位置的实际缺口大小，网络的总体最大流上限为 $K$ 。当且仅当网络的最大流精准等于 $K$ 时，才意味着每个缺水结点的管道全部达到了容量上限，即所有位置的缺口都被完整填补。此时网络流算法在达到最大流状态时所产生的总费用，即为所有缺口被补齐时所需的最小操作次数。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main(){
5

6
}

多重差分题目收集#

在最基础的差分模型中，核心操作通常被定义为：对指定区间内的所有元素 同步累加单一常数项 。此类操作在差分序列中具有极高的稀疏性，仅需在区间端点进行两次标量修改即可完成，逻辑结构清晰且直观。然而，在进阶的竞赛题目中，区间内的增量序列并不总是保持恒定，而是往往表现为 遵循特定代数规律变化的数列 。

当区间增量具有明确的函数特征（如等差序列、等比序列或低阶多项式函数）时，单一维度的差分将难以将其完全解耦。此时需引入 多重差分 技巧：通过对原始序列执行连续阶次的差分处理，将高阶的区间变化逐步剥离，直至其退化为底层序列中的 常数级区间修改 。

其核心逻辑在于 连续差分具有降低增量数列变化规律阶数的效应 。以区间累加等差数列为例，一次差分操作可将线性增长的增量转化为分段常数，而二次差分则能将该常数进一步离散化为仅在特定位置存在的数值脉冲。通过这种层级化的降阶，复杂的动态更新被压缩为极少数关键节点的数值修正，最终再通过等量的多重前缀和还原，即可实现从差分域到原始数据域的完备重构。

真寻的高效清理#

题目链接

Problem Statement#

真寻的房间由 $n$ 行 $m$ 列的方砖组成，第 $i$ 行第 $j$ 列的方砖上初始灰尘数量为 $a_{i,j}$ 。真寻将会使用 $k$ 次清理炸弹。第 $i$ 次操作她会在第 $x_i$ 行第 $y_i$ 列的方砖上使用能量值为 $p_i$ 的清理炸弹，其清理效果如下：

中心点 $(x_i, y_i)$ ：灰尘数量减少 $p_i^2$
外围第 1 圈：灰尘数量减少 $(p_i - 1)^2$
外围第 2 圈：灰尘数量减少 $(p_i - 2)^2$
$\ldots$
外围第 $(p_i - 1)$ 圈：灰尘数量减少 $1^2 = 1$

需要注意以下两点：

灰尘数量不能为负数。如果某块方砖上的灰尘数量小于要减少的量，则该方砖灰尘数量变为 $0$ 。
外围第 $d$ 圈是指所有满足 $\max(|x-x_i|, |y-y_i|) = d$ 的方砖。

请输出每个方砖最终的灰尘数量。

Constraints#

$1 \leq n, m, p_i \leq 10^3$
$1 \leq k \leq 10^6$
$0 \leq a_{i, j} \leq 10^12$
$1 \leq x_i \leq n$
$1 \leq y_i \leq m$

Input#

输入包含多行：

第一行包含三个整数 $n$ 、 $m$ 和 $k$ ，分别表示方砖行数、列数及操作次数。
接下来 $n$ 行，每行 $m$ 个整数，表示初始灰尘数组 $a_{i,j}$ 。
接下来 $k$ 行，每行包含三个整数 $x_i, y_i, p_i$ ，描述一次清理操作。

$n \quad m \quad k$

$a_{1,1} \quad a_{1,2} \quad \ldots \quad a_{1,m}$

$\ldots$

$x_1 \quad y_1 \quad p_1$

$\ldots$

Output#

输出 $n$ 行，每行 $m$ 个整数，表示 $k$ 次操作后每块方砖上最终的灰尘数量。

Sample Input 1#

Sample Output 1#

Sample Input 2#

6 7 3
6 4 7 8 4 6 1
4 5 4 6 7 5 9
1 4 3 0 7 1 3
4 6 0 7 9 0 0
1 2 3 4 4 5 8
4 7 6 8 7 4 9
5 5 3
2 3 4
3 6 2

Sample Output 2#

2 0 0 0 0 5 1
0 0 0 0 2 3 8
0 0 0 0 1 0 1
0 2 0 0 0 0 0
0 1 1 0 0 0 7
4 7 5 4 3 0 8

题目要点解析#

从题目描述来看，清理炸弹的 清理效果 具有极强的空间对称性和数学规律。由于 差分数组 本质上是原数组的离散导数，这种具有固定代数规律的变化量，在经过 高阶差分 处理后，往往能被简化为极少数特征点上的变动。与其直接维护原数组并执行 $O(p^2)$ 的区域更新，不如通过维护差分数组，记录每一处数值发生改变的 变化点 ，最后利用 前缀和操作 进行复原。

如果对单次清理操作产生的增量矩阵先进行一次 二维差分（或者分别执行一次横向和竖向的差分），我们可以观察到所得的结果表现为四条呈 X 型对称分布的等差数列 。这意味着 差分的结果仍然具备规律 ，因此可以考虑再次进行差分。然而，这里的难点在于 如何选择差分方向 。由于这些等差数列是沿 对角线 分布的，如果直接使用斜向差分，虽然能简化其中一条对角线，但另一条正交方向的等差数列就没办法被简化。

为了解决这个方向上的冲突，我们可以将这些对称的变化量从原图中拆分出来，分别进行维护。具体做法是准备两个 独立的差分辅助数组：一个专门维护从 左上到右下 方向的差分结果，另一个则维护从 左下到右上 方向的差分结果。这样，对于每一次炸弹操作，我们只需要在两个数组对应的位置上进行标记。通过这种拆分逻辑，可以将原本互相干扰的两个方向解耦，使它们在各自的差分维度下都能被简化。

在最终复原时，我们首先沿着各自对应的斜向方向进行 第二次前缀和复原 ，将差分标记还原为等差数列。随后，将这两个数组的结果进行叠加，再统一执行一次 二维前缀和处理（或者分别进行一次横向和竖向的前缀和），从而得到每个位置累计的总清理量 $S_{i,j}$ 。最终方砖的灰尘残余量通过以下公式计算：

\text{result}_{i,j} = \max(0, a_{i,j} - S_{i,j})

这种方法巧妙地利用了 斜向差分 对对角线等差序列的压缩能力，通过将不同方向的规律 拆分再叠加 ，成功绕开了直接在二维平面上处理复杂增量的难题。整个过程只需要在标记时花费 $O(k)$ 的时间，并在最后通过 $O(n \cdot m)$ 的扫描完成复原，在 时间复杂度 与 逻辑严密性 上都达到了很好的平衡。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main(){
5

6
}

有趣的组合数组#

题目链接

题目要点解析#

杨辉三角组合数学差分

等式条件变为不等条件相关题目收集#

在许多复杂的计数与组合问题中，等式条件往往显得过于严苛且缺乏单调性 ，直接对其进行状态定义或转移通常会面临极高的思维难度。相比之下，不等式的限制条件则更为宽松 ，且往往具备天然的单调特性，这使得我们可以利用双指针、二分查找或动态规划等手段更高效地处理。因此，我们经常采用一种类似差分的转换思路，将原本难以企及的精确等式条件，拆解为两个容易统计的不等式之差：

\text{count}(\text{ans} = k) = \text{count}(\text{ans} \leq k) - \text{count}(\text{ans} \leq k-1)

这种技巧的核心逻辑在于，我们不再死磕 恰好等于某个数 这个严格的条件，而是去统计 不超过某个数 这个较为宽松的条件，通过放宽约束条件来换取计算上的便利性。由于不等式计数通常允许我们使用滑动窗口等具备单调性的算法，往往能将原本 $O(n^2)$ 甚至更高复杂度的做法强行简化。

事实上，这种从精确判定向范围统计过渡的策略，其本质是对计数维度 进行前缀化处理 。这一思想在组合数学中具有深远的意义，二项式反演 便是该逻辑的高阶体现。二项式反演通过建立 “至多/至少” 与 “恰好” 之间的代数映射，利用广义容斥原理将难以直接刻画的属性分布转化为累积量的组合叠加。尽管其底层数学结构更为精精密，但其核心诉求始终在于通过放宽约束来换取统计上的可行性。

数学期望的尾概率公式#

在求解数学期望时，我们常常会遇到因状态过于复杂而难以刻画的情况。为了打破传统求解方法带来的计算僵局，算法竞赛中通常会引入一种 将点概率转化为范围概率 的思维模型，通过 重新构建期望的计算维度 来简化逻辑。

中学阶段经常会遇到求解数学期望的问题，我们常用的期望求解公式是：

E[X] = \sum_{i=1}^{\infty} i \cdot P(X = i) = 1 \cdot P(X=1) + 2 \cdot P(X=2) + 3 \cdot P(X=3)

而竞赛当中我们经常使用期望的 尾概率公式：

E[X] = \sum_{i=1}^{\infty} P(X \geq i) = P(X \geq 1) + P(X \geq 2) + P(X \geq 3)

原因是中学阶段的公式中包含的 $P(X = i)$ 求解的是 “恰好等于” 的概率，在算法竞赛中通常难以维护，因此一般使用包含 $P(X \geq i)$ 的尾概率公式。而这个公式的推导非常简单，只需要用到 初中的因式分解 即可。

我们可以将公式排列为一个 三角形矩阵：

\begin{aligned} E[X] = \quad & P(X=1) \\ + \quad & P(X=2) + P(X=2) \\ + \quad & P(X=3) + P(X=3) + P(X=3) \end{aligned}

传统的求解方式是 横向求和 ，即先算出每一行的结果再相加。现在我们 改变视角 ，将这个矩阵 纵向按列合并：

第一列包含了所有可能发生的事件概率

P(X = 1) + P(X = 2) + P(X = 3) = P(X \geq 1)

第二列去掉了 $X = 1$ 的情况，包含了所有大于等于 $2$ 的事件概率

P(X=2) + P(X=3) = P(X \geq 2)

第三列去掉了 $X = 1, 2$ 的情况，包含了所有大于等于 $3$ 的事件概率

P(X = 3) = P(X \geq 3)

不难发现，将所有纵列的结果相加，其总和依然与原式完全相等。这种通过 改变求和顺序 的手法，在统计学中相当于把原本横向切割的概率条改为了 纵向叠加的后缀和 。它巧妙地将互相制约的点概率问题转化为了 具备优美单调性的范围统计 ，从而极大地降低了复杂极值问题的状态定义与转移难度。

K种整数子数组#

题目链接

Problem Statement#

给定一个正整数数组 $nums$ 和一个整数 $k$ ，返回 $nums$ 中 「好子数组」 的数目。如果 $nums$ 的某个子数组中不同整数的个数恰好为 $k$ ，则称 $nums$ 的这个连续、不一定不同的子数组为「好子数组」。

子数组 是数组的连续部分。

Constraints#

$1 \leq nums.length \leq 2 * 10^4$
$1 \leq nums[i], k \leq nums.length$

Input#

输入包含两行：

第一行包含两个整数 $N$ 和 $k$ 。
第二行包含 $N$ 个整数，表示数组中的元素。

$N \quad k$

$nums_1 \quad nums_2 \quad \ldots \quad nums_N$

Output#

输出一个整数，表示好子数组的数目。

Sample Input 1#

5 2
1 2 1 2 3

Sample Output 1#

Sample Input 2#

5 3
1 2 1 3 4

Sample Output 2#

题目要点解析#

在处理子数组计数问题时，一个自然的尝试是使用 滑动窗口 技巧。然而，滑动窗口的适用性严格受限于问题的 单调性 。只有当窗口状态随边界移动呈现出 “越长越满足” 或 “越短越满足” 的趋势时，窗口的扩张与收缩才有据可依。通常情况下，这类具备单调性的约束表现为 “至少 k 种” 或 “至多 k 种” 。

在本题中，核心目标是统计 “恰好有 k 个不同整数” 的子数组。由于 “恰好” 这一等式条件本身不具备单调性，窗口的任何移动都可能导致状态在合法与非法之间随机切换，因此无法直接利用滑动窗口进行稳定维护。这种维护性的缺失，正是该类题目难以直接求解的根源。

为了破解这一困局，我们可以借助上面提到过的 广义差分思路 ，将严苛的等式约束差分为具备单调性的不等式条件。通过将恰好型计数转化为两个 逻辑一致仅参数不同 的不等式计数：

\text{count}(\text{distinct} = k) = \text{count}(\text{distinct} \le k) - \text{count}(\text{distinct} \le k-1)

在这种转化下，原命题被拆解为对 同一种不等式判定逻辑 的两次调用。由于 “至多 $k$ 个不同整数” 这一判定条件具有完美的单调性，我们可以通过复用同一套滑动窗口算法逻辑，分别计算出两个累积区间对应的子数组数量，再通过作差间接推导出 “恰好 k 个不同整数” 的精确结果。

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int MAXN = 2e4 + 100;
4
int N, k;
5
int nums[MAXN];
6

7
int count(int k, int* a){
8
    int left = -1, pre = 0, ans = 0;
9
    unordered_map<int, int> counts;
10
    for (int right = 0; right < N; right ++){
11
        counts[a[right]] += 1;
12
        while (left <= right && (int)counts.size() > k){
13
            counts[a[++left]]--;
14
            if (!counts[a[left]])
15
                counts.erase(a[left]);
16
        }
17
        ans += right - left;
18
    }
19

20
    return ans;
21
}
22

23
int main() {
24
    cin >> N >> k;
25
    for (int i = 0; i < N; i++){
26
        cin >> nums[i];
27
    }
28

29
    cout << count(k, nums) - count(k - 1, nums);
30
}

最值的数学期望#

题目链接

Problem Statement#

有 $n$ 个六面骰子，编号为 $1 \sim n$ 。骰子 $i$ 的六个面上分别写着数值 $A_{i,1}, A_{i,2}, \ldots, A_{i,6}$ 。

现在将这 $n$ 个骰子同时掷出。请计算所有骰子朝上面数值的 最大值 的数学期望，结果对 $998244353$ 取模。

每个骰子的面是独立且等概率出现的。

Constraints#

$1 \leq n \leq 10^5$
$1 \leq A_{i,j} \leq 10^9$
所有输入均为整数

Input#

输入包含多行：

第一行包含一个整数 $n$ 。
接下来 $n$ 行，每行包含 $6$ 个整数，依次表示第 $i$ 个骰子的面数值。

$n$

$A_{1,1} \quad A_{1,2} \quad \ldots \quad A_{1,6}$

$A_{2,1} \quad A_{2,2} \quad \ldots \quad A_{2,6}$

$\ldots$

$A_{n,1} \quad A_{n,2} \quad \ldots \quad A_{n,6}$

Output#

输出一个整数，表示最大值的数学期望。

Sample Input 1#

2
1 1 4 4 4 4
1 1 1 3 3 3

Sample Output 1#

332748121

Sample Input 2#

2
1 1 1 1 1 1
2 2 2 2 2 2

Sample Output 2#

Sample Input 3#

8
55 76 80 21 34 28
82 84 2 32 56 17
11 57 37 28 39 18
47 2 97 25 75 29
72 45 22 75 26 81
6 79 16 68 68 40
31 80 68 57 18 55
49 10 63 91 93 40

Sample Output 3#

213725517

题目要点解析#

尾概率公式

区间求和变为前缀求和相关题目收集#

在许多的算法问题中，直接处理区间求和往往不够直观 ，不仅实现复杂，还容易在枚举区间的过程中产生大量重复的计算；而当我们将问题转化为 前缀求和形式 后，整体结构通常会变得更加清晰，计算过程也更加高效。因此，在处理涉及区间统计的问题时，一个非常常见的思路就是 先将区间求和转写为前缀和之间的差值关系 。通过引入前缀和数组，我们可以把所有区间约束统一表示为端点之间的关系，从而简化整体的推导过程：

\sum_{i = l}^{r} a_i = pre[r] - pre[l-1]

这种技巧的核心在于，我们可以用 全局累积信息代替局部区间计算 。通过预处理前缀和数组，我们能够在 $O(1)$ 的时间内得到任意区间的和，使原本需要枚举整段区间的操作被压缩为一次简单的差值计算。这样不仅可以显著降低时间复杂度，也能够让很多原本分散的区间操作被统一到同一种表达框架下，从而方便后续的建模与优化。

在完成区间到前缀的转化之后，问题往往会进一步转化为 两个前缀值之间的关系问题 。这时我们就可以借助类似两数之和的思想来进行处理：固定右端点的信息，动态维护左端点可能出现的前缀值 。在一些题目中，这种维护过程可以通过 双指针 来实现，例如保持右端点单调移动，同时用左指针维护满足条件的范围；而在另一些问题中，也可能需要借助 哈希表 等数据结构来统计满足条件的前缀值数量。

从更宏观的角度来看，将区间求和转化为前缀和之差本质上是一种 降维过程 。它将涉及多个变量的区间动态累加，成功映射为仅涉及两个前缀值的简单运算。这种转化在不改变问题原本的数学性质的前提下，极大地精简了统计规模。由于前缀和之差在逻辑上完全等价于区间累加和，将区间和转换为前缀和几乎是处理此类问题的必然思路 。任何能直接在原始问题上生效的解法，在转化后的框架下不仅完全兼容，且往往能展现出更优的处理效率。

数组的递增划分#

题目链接

Problem Statement#

我们称一个分割整数数组的方案是好的，当它满足：

数组被分成三个非空连续子数组，从左至右分别命名为 left ，mid ，right 。
left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。

给你一个非负整数数组 nums ，请你返回好的分割 nums 方案数目。

由于答案可能会很大，请你将结果对 $10^9 + 7$ 取余后返回。

Constraints#

$3 \leq nums.length \leq 10^5$
$0 \leq nums[i] \leq 10^4$

Input#

输入包含两行：

第一行包含一个整数 $N$ ，表示数组的长度。
第二行包含 $N$ 个整数，表示数组中的元素。

$N$

$nums_1 \quad nums_2 \quad \ldots \quad nums_N$

Output#

输出一个整数表示答案。

Sample Input 1#

3
1 1 1

Sample Output 1#

Sample Input 2#

6
1 2 2 2 5 0

Sample Output 2#

题目要点解析#

这道题要求把数组 nums 分割成三个 非空连续子数组 left 、mid 、right，并满足两个条件：sum(left) ≤ sum(mid) 且 sum(mid) ≤ sum(right) 。由于需要频繁比较区间和，如果每次重新计算会非常低效，因此可以先构建 前缀和数组 来简化计算。设 pre[i] 表示数组前 $i$ 个元素的和，那么整个数组的总和就是 pre[n] 。

当数组在位置 left 和 mid 处分割时，三个部分的和可以用前缀和直接表示：left 的和为 pre[left] ，mid 的和为 pre[mid] - pre[left] ，right 的和为 pre[n] - pre[mid] 。这样一来，只需要把题目中的条件转化为前缀和之间的不等式即可。

首先考虑条件 sum(left) ≤ sum(mid) 。代入前缀和表达式可以得到：

pre[left] \leq pre[mid] - pre[left]

整理后得到：

2 \times pre[left] \leq pre[mid]

这说明当 left 固定时，mid 的前缀和至少需要达到 2 * pre[left] 。

接下来考虑第二个条件 sum(mid) ≤ sum(right) 。同样代入前缀和表达式可以得到：

pre[mid] - pre[left] \leq pre[n] - pre[mid]

整理后得到：

2 \times pre[mid] \leq pre[left] + pre[n]

进一步可以写成：

pre[mid] \leq \frac{pre[left] + pre[n]}{2}

因此在 left 固定时，mid 的前缀和必须满足如下范围：

2 \times pre[left] \leq pre[mid] \leq \frac{pre[left] + pre[n]}{2}

接下来可以得到一个非常重要的 剪枝条件 。因为 mid 的最小值是 2 * pre[left] ，如果这个值已经大于右侧上界 (pre[left] + pre[n]) / 2 ，那么就不存在合法的 mid 。将不等式整理后可以得到：

3 \times pre[left] \leq pre[n]

也就是说，当 pre[left] 满足下面条件：

pre[left] > \frac{pre[n]}{3}

无论怎样选择 mid 都无法满足条件，因此可以直接停止枚举 left。

在算法实现时，可以先计算前缀和数组，然后枚举 left 的位置。当 left 固定后，mid 的取值范围实际上对应前缀和数组中一段连续的区间：下界是第一个满足 pre[mid] ≥ 2 * pre[left] 的位置，而上界是最后一个满足 pre[mid] ≤ (pre[left] + pre[n]) / 2 的位置。由于前缀和数组是单调递增的，因此可以使用 二分查找 来快速定位这两个边界。最后题目要求结果对 $10^9 + 7$ 进行取模。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main(){
5

6
}

指定区间累加和#

题目链接

Problem Statement#

给定一个整数 $N$ 和长度为 $M$ 的整数序列：

L = (L_1, L_2, \ldots, L_M) \quad R = (R_1, R_2, \ldots, R_M) \quad S = (S_1, S_2, \ldots, S_M)

确定是否存在一个长度为 $N$ 的正整数序列 $A$ 满足以下条件：

\sum_{j=L_i}^{R_i} A_j = S_i (1 \leq i \leq M)

如果存在这样的序列，找到 $A$ 的最小可能和。

Constraints#

$1 \leq N, M \leq 4000$
$1 \leq L_i \leq R_i \leq N$
$1 \leq S_i \leq 10^9$
所有输入均为整数

Input#

输入包含多行：

第一行包含两个整数 $N$ 和 $M$ 。
接下来的 $M$ 行，每行包含三个整数 $L$ 、 $R$ 和 $S$ 。

$N \quad M$

$L_1 \quad R_1 \quad S_1$

$L_2 \quad R_2 \quad S_2$

$\ldots$

$L_M \quad R_M \quad S_M$

Output#

如果不存在满足条件且长度为 $N$ 的正整数序列 $A$ ，则输出 -1 ；否则，输出 $A$ 的最小可能总和。

Sample Input 1#

Sample Output 1#

Sample Input 2#

1 2
1 1 1
1 1 2

Sample Output 2#

-1

Sample Input 3#

Sample Output 3#

题目要点解析#

差分约束

双边条件变为单边条件相关题目收集#

在算法竞赛中，我们经常会遇到需要统计满足某种 双边约束 的组合数量、子数组个数或元素分布的问题。这类问题的核心矛盾通常体现在条件的双向限制上，即要求某个统计量 $T$ 必须同时受限于给定的上下界：

\text{lower} \leq T \leq \text{upper}

若直接对所有情况进行合法性检测，往往会面临极高的算法复杂度。解决此类问题的关键在于将原本的 双边不等式约束 转化为更容易处理的 单边不等式逻辑 。原本的条件 $\text{lower} \leq T \leq \text{upper}$ 可以等价地解构为两个单边条件的交集，即 $T \leq \text{upper}$ 与 $T \geq \text{lower}$ 。在此基础上，通过引入计数函数 $f(X)$ 来表示满足单边约束 $T \leq X$ 的样本总量，原命题即可转化为标准的差分形式：

\text{count}(\text{lower} \leq T \leq \text{upper}) = f(\text{upper}) - f(\text{lower} - 1)

这种转化的核心逻辑在于：通过主动放宽约束边界，将双向限制问题降维成易于维护的单边单调性问题 。在这种视角下，我们不再受困于双向边界的同步校验，而是通过解决约束宽松且具有前缀性质的单边统计问题，并利用差分技巧还原出精确的双边计数结果。这种以退为进的逻辑转化，能有效利用单向条件的单调性来适配双指针或二分等高效算法，将棘手的双边判定条件，重新包装为简单的单边判定条件。

值得一提的是，这类双边约束条件天然契合数位 DP相关问题。例如统计某个区间内满足特定条件的数字，原本的双边约束可以直接转化为单边约束的计数函数 $f(X)$ 。然而数位 DP 中出现的上下界往往非常大，如果直接计算 $f(\text{lower}-1)$ 可能涉及高精度计算。为了避免这种情况，我们可以先计算 $f(\text{upper}) - f(\text{lower})$ ，再单独判断 $lower$ 是否满足要求。

统计公平的数对#

题目链接

Problem Statement#

给你一个下标从 $0$ 开始、长度为 $n$ 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 $(i, j)$ 数对满足以下情况，则认为它是一个 公平数对：

$0 <= i < j < n$
$lower <= nums[i] + nums[j] <= upper$

Constraints#

$1 \leq nums.length \leq 10^5$
$nums.length == n$
$-10^9 \leq nums[i] \leq 10^9$
$-10^9 \leq lower \leq upper \leq 10^9$

Input#

输入包含两行：

第一行包含三个整数 $N$ 、 $lower$ 和 $upper$ 。
第二行包含 $N$ 个整数，表示数组中的元素。

$N \quad lower \quad upper$

$nums_1 \quad nums_2 \quad \ldots \quad nums_N$

Output#

输出一个整数表示答案。

Sample Input 1#

6 3 6
0 1 7 4 4 5

Sample Output 1#

Sample Input 2#

5 11 11
1 7 9 2 5

Sample Output 2#

题目要点解析#

这道题要求统计满足 $i < j$ 且 lower ≤ nums[i] + nums[j] ≤ upper 的数对数量。直接枚举所有 $(i, j)$ 的时间复杂度是 $O(n^2)$ ，显然无法通过 $10^5$ 的数据规模，因此需要换一种思路。

一个常见的技巧是把区间计数问题转化为 两个前缀计数之差 。设 count(x) 表示满足 nums[i] + nums[j] ≤ x 的数对数量，那么题目要求的答案就可以表示为：

count(upper) - count(lower - 1)

因此问题就转化为了如何高效计算 count(x) 。

为了计算 count(x) ，可以先对数组进行排序。排序之后，如果固定左端点 $i$ ，随着 $j$ 的增大，nums[i] + nums[j] 也会单调增加，因此可以使用 双指针 来统计合法的数对数量。

通过这样的方式就可以在线性时间内计算出 count(x) 。最后分别计算 count(upper) 和 count(lower - 1) ，两者相减即可得到最终答案。整个算法的时间复杂度为 $O(n \log n)$ ，双指针统计部分为 $O(n)$ 。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main(){
5

6
}

参考文献列表#

【ACM 算法随笔】差分数组与差分思想

https://xingguang641.com/posts/acm/acm-note/difference-idea/

作者

星光

发布于

2025-11-25

许可协议

CC BY-NC-SA 4.0

【ACM 算法随笔】二分查找与二分答案

【博客指南】如何创建一个独立页面