差分专题练习 ——基于罗勇军老师的《蓝桥杯算法入门C/C++》

一、1.重新排序 - 蓝桥云课

算法代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;int a[N], d[N], cnt[N];int main() {int n; scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);int m; scanf("%d", &m);long long ans1 = 0, ans2 = 0;// 处理区间查询，更新差分数组 d[]while (m--) {int L, R; scanf("%d%d", &L, &R);d[L]++; d[R+1]--;}// 通过差分数组 d[] 还原累加次数 cnt[]cnt[0] = d[0];for (int i = 1; i <= n; i++) cnt[i] = cnt[i-1] + d[i];// 计算未排序时的累加结果 ans1for (int i = 1; i <= n; i++) ans1 += (long long)a[i] * cnt[i];// 排序 a[] 和 cnt[]，计算排序后的累加结果 ans2sort(a + 1, a + 1 + n);sort(cnt + 1, cnt + 1 + n);for (int i = 1; i <= n; i++) ans2 += (long long)a[i] * cnt[i];// 输出结果printf("%lld\n", ans2 - ans1);return 0;
}

代码思路解析

1. 问题背景

这段代码的目标是高效处理多个区间查询，并对数组 a[] 进行累加操作。通过差分数组 d[] 优化区间修改，避免直接遍历区间内的每个元素。

2. 核心思路

差分数组：记录区间修改的起点和终点，避免逐个修改。
前缀和：通过差分数组还原每个位置的累加次数 cnt[]。
排序与匹配：通过排序 a[] 和 cnt[]，计算最小和最大累加结果。

3. 代码实现步骤

输入数组 a[] 和查询次数 m：
- 读取数组 a[] 和查询次数 m，初始化差分数组 d[] 和累加次数数组 cnt[]。
处理区间查询：
- 对每个查询 [L, R]，更新差分数组 d[]：
  - d[L]++：区间起点加1。
  - d[R+1]--：区间终点外减1（抵消后续影响）。
还原累加次数 cnt[]：
- 通过差分数组 d[] 计算每个位置的累加次数 cnt[]：
  - cnt[i] = cnt[i-1] + d[i]。
计算累加结果：
- 未排序时：直接计算 ans1 = sum(a[i] * cnt[i])。
- 排序后：将 a[] 和 cnt[] 排序，计算 ans2 = sum(a[i] * cnt[i])。
输出结果：
- 输出排序前后的差值 ans2 - ans1。

4. 复杂度分析

差分数组更新：每个查询 O(1)，总复杂度 O(m)。
累加次数还原：遍历数组 O(n)。
排序：O(nlog⁡n)。
总复杂度：O(m+nlog⁡n)，适用于大规模数据处理。

5. 关键点

差分数组：高效记录区间修改。
前缀和：快速还原累加次数。
排序优化：通过排序匹配最小和最大累加结果。

通过上述思路和代码，可以高效解决区间累加问题。

关于 `sort` 的排序规则和对应问题

1. `sort` 的默认行为

默认排序规则：C++ 中的 sort 函数默认是按升序排序的。
排序依据：sort 会根据元素的值进行排序，而不是它们的原始位置。

2. 排序后的对应问题

在代码中，a[] 和 cnt[] 分别被排序：

sort(a + 1, a + 1 + n);      // 对 a[] 排序
sort(cnt + 1, cnt + 1 + n);  // 对 cnt[] 排序

排序后的结果：
- a[] 和 cnt[] 分别按升序排列。
- 排序后，a[i] 和 cnt[i] 的对应关系被打破，因为它们各自独立排序。

3. 为什么排序后仍然有效？

目标：代码的目标是计算两种累加结果的差值：
- 未排序时：ans1 = sum(a[i] * cnt[i])，即原始对应关系下的累加结果。
- 排序后：ans2 = sum(a[i] * cnt[i])，即排序后的累加结果。
数学原理：
- 排序后，a[] 和 cnt[] 分别按升序排列，此时 ans2 是 a[] 和 cnt[] 的最小匹配累加结果。
- 由于 a[] 和 cnt[] 都是升序排列，ans2 是 a[] 和 cnt[] 的最小可能累加和。
- 差值 ans2 - ans1 反映了排序对累加结果的影响。

4. 排序的意义

未排序时：ans1 是基于原始对应关系的累加结果。
排序后：ans2 是基于最小匹配的累加结果。
差值 ans2 - ans1：
- 如果 ans2 < ans1，说明排序后的累加结果更小。
- 如果 ans2 > ans1，说明排序后的累加结果更大。
- 差值反映了排序对累加结果的影响。

5. 代码的逻辑

未排序时：直接计算原始对应关系下的累加结果 ans1。
排序后：计算最小匹配的累加结果 ans2。
输出差值：ans2 - ans1，反映排序对累加结果的影响。

6. 示例说明

假设：

a[] = [3, 1, 2]
cnt[] = [2, 3, 1]

未排序时：

ans1 = 3*2 + 1*3 + 2*1 = 6 + 3 + 2 = 11

排序后：

a[] = [1, 2, 3]
cnt[] = [1, 2, 3]
ans2 = 1*1 + 2*2 + 3*3 = 1 + 4 + 9 = 14

差值：

ans2 - ans1 = 14 - 11 = 3

二、 P1819 - [NewOJ Week 6] 推箱子 - New Online Judge

算法代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; // 定义 long long 类型别名为 ll，方便使用
const int N = 1e6 + 10; // 定义常量 N 为 1000010，表示数组的最大大小ll d[N], a[N], sum[N]; // 定义差分数组 d[]，原数组 a[]，前缀和数组 sum[]int main() {int n, h; scanf("%d%d", &n, &h); // 读取障碍物的尺寸 n 和箱子的高度 h// 处理每一列的空白区域for (int i = 1; i <= n; i++) {int li, hi;scanf("%d%d", &li, &hi); // 读取第 i 列空白区域的起始位置 li 和结束位置 hi// 更新差分数组 d[]d[li]++;      // 从第 li 行开始，空白区域的数量增加 1d[hi + 1]--;  // 从第 hi+1 行开始，空白区域的影响结束}// 用差分数组 d[] 计算原数组 a[]for (int i = 1; i <= n; i++) {a[i] = a[i - 1] + d[i - 1]; // 计算第 i 行的空白数量}// 用原数组 a[] 计算前缀和数组 sum[]for (int i = 1; i <= n; i++) {sum[i] = sum[i - 1] + a[i]; // 计算前 i 行的空白数量总和}// 找到连续 h 行的最大空白数量总和ll ans = sum[h - 1]; // 初始化 ans 为前 h 行的空白数量总和for (int left = 1; left + h - 1 <= n; left++) {// 计算从 left 行开始的连续 h 行的空白数量总和ans = max(ans, sum[left + h - 1] - sum[left - 1]);}// 输出需要清理的障碍物面积cout << (ll)n * h - ans << endl; // 总障碍物面积减去最大空白面积return 0;
}

代码思路

1. 问题分析

问题描述：在一个高度为 H 的箱子的前方有一个长和高均为 N 的障碍物。每一列有一个连续的空白区域，范围是 [l_i, h_i]。需要找到一条高度为 H 的通道，使得箱子可以直接推出去。输出最少需要清理的障碍物面积。
核心目标：找到连续 H 行的空白区域总和最大的区间，然后用总障碍物面积减去这个最大空白面积，得到需要清理的最小障碍物面积。

2. 解决思路

空白区域的表示：每一列的空白区域 [l_i, h_i] 会影响多行的空白数量。
差分数组优化：使用差分数组 d[] 来高效记录每一列空白区域对行的贡献。
前缀和优化：通过前缀和数组 sum[] 快速计算任意区间的空白数量总和。
滑动窗口：遍历所有可能的连续 H 行区间，找到空白数量总和最大的区间。

代码逻辑流程

1. 初始化

定义常量 N 为 1000010，表示数组的最大大小。
定义 long long 类型的别名 ll，用于处理大整数。
定义差分数组 d[]、原数组 a[] 和前缀和数组 sum[]。

2. 输入处理

读取障碍物的尺寸 n 和箱子的高度 h。
循环读取每一列的空白区域 [l_i, h_i]，并更新差分数组 d[]：
- d[l_i]++：从第 l_i 行开始，空白区域的数量增加 1。
- d[h_i + 1]--：从第 h_i + 1 行开始，空白区域的影响结束。

3. 计算原数组 `a[]`

通过差分数组 d[] 计算原数组 a[]，表示每一行的空白数量：
- a[i] = a[i - 1] + d[i - 1]。

4. 计算前缀和数组 `sum[]`

通过原数组 a[] 计算前缀和数组 sum[]，表示前 i 行的空白数量总和：
- sum[i] = sum[i - 1] + a[i]。

5. 找到最大空白区域

初始化 ans 为前 h 行的空白数量总和。
使用滑动窗口遍历所有可能的连续 h 行区间，找到空白数量总和最大的区间：
- ans = max(ans, sum[left + h - 1] - sum[left - 1])。

6. 输出结果

计算需要清理的障碍物面积：总障碍物面积 - 最大空白面积。
输出结果：cout << (ll)n * h - ans << endl;。

代码逻辑总结

输入处理：
- 读取障碍物的尺寸 n 和箱子的高度 h。
- 读取每一列的空白区域 [l_i, h_i]，并更新差分数组 d[]。
差分数组还原：
- 通过差分数组 d[] 计算原数组 a[]，表示每一行的空白数量。
前缀和计算：
- 通过原数组 a[] 计算前缀和数组 sum[]，表示前 i 行的空白数量总和。
滑动窗口查找最大空白区域：
- 遍历所有可能的连续 h 行区间，找到空白数量总和最大的区间。
输出结果：
- 计算并输出需要清理的最小障碍物面积。

代码优化点

差分数组：将区间更新操作从 O(NH) 优化到 O(N)。
前缀和数组：将区间查询操作从 O(NH) 优化到 O(N)。
滑动窗口：通过滑动窗口遍历所有可能的连续 h 行区间，时间复杂度为 O(N)。

代码适用场景

适用于处理大规模数据（n 和 h 最大为 1000000）。
通过差分数组和前缀和优化，能够高效解决区间更新和查询问题。

通过以上思路和逻辑，代码能够高效地解决推箱子问题，找到需要清理的最小障碍物面积。

三、 1.棋盘 - 蓝桥云课

算法代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2200;
int a[N][N],d[N][N];
int n,m;void insert(int x1,int y1,int x2,int y2)
{d[x1][y1]++;d[x1][y2+1]--;d[x2+1][y1]--;d[x2+1][y2+1]++;
}int main()
{cin>>n>>m;while(m--){int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;insert(x1,y1,x2,y2);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[i][j]=d[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];cout<<(a[i][j]&1);}cout<<endl;}return 0;
}

代码思路

1. 问题分析

问题描述：给定一个 n x n 的矩阵，初始时所有元素为 0。进行 m 次操作，每次操作将一个子矩阵 [x1, y1] 到 [x2, y2] 内的所有元素加 1。最后输出每个元素的值是否为奇数（1 表示奇数，0 表示偶数）。
核心目标：高效处理多次区间更新操作，并快速查询每个元素的值。

2. 解决思路

二维差分数组：使用二维差分数组 d[][] 来高效记录每次区间更新操作。
前缀和还原：通过二维前缀和还原原数组 a[][]，表示每个元素的值。
奇偶性判断：输出每个元素的值是否为奇数。

代码逻辑流程

1. 初始化

定义常量 N 为 2200，表示矩阵的最大大小。
定义原数组 a[][] 和差分数组 d[][]。

2. 插入操作函数 `insert`

定义函数 insert(x1, y1, x2, y2)，用于更新差分数组 d[][]：
- d[x1][y1]++：表示从 (x1, y1) 开始的区域增加 1。
- d[x1][y2 + 1]--：表示从 (x1, y2 + 1) 开始的区域减少 1。
- d[x2 + 1][y1]--：表示从 (x2 + 1, y1) 开始的区域减少 1。
- d[x2 + 1][y2 + 1]++：表示从 (x2 + 1, y2 + 1) 开始的区域增加 1。

3. 主函数

读取矩阵的大小 n 和操作次数 m。
循环处理每次操作：
- 读取子矩阵的范围 [x1, y1] 到 [x2, y2]。
- 调用 insert(x1, y1, x2, y2) 更新差分数组 d[][]。

4. 还原原数组 `a[][]`

使用二维前缀和还原原数组 a[][]：
- a[i][j] = d[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]。
- 这表示 (i, j) 位置的值等于差分数组的值加上左边和上边的值，减去左上角的值。

5. 输出结果

遍历矩阵的每个元素，输出其值是否为奇数：
- a[i][j] & 1：判断 a[i][j] 的最低位是否为 1（奇数）。

代码逻辑总结

初始化：
- 定义矩阵大小 n 和操作次数 m。
- 定义原数组 a[][] 和差分数组 d[][]。
插入操作：
- 每次操作调用 insert(x1, y1, x2, y2)，更新差分数组 d[][]。
还原原数组：
- 使用二维前缀和还原原数组 a[][]。
输出结果：
- 遍历矩阵的每个元素，输出其值是否为奇数。

代码优化点

二维差分数组：将区间更新操作从 O(N^2) 优化到 O(1)。
二维前缀和：将区间查询操作从 O(N^2) 优化到 O(1)。
奇偶性判断：通过位运算快速判断每个元素的值是否为奇数。

代码适用场景

适用于处理大规模矩阵的多次区间更新操作。
通过二维差分数组和前缀和优化，能够高效解决区间更新和查询问题。

代码示例

输入

4 2
1 1 2 2
2 2 3 3

输出

解释

第一次操作将子矩阵 [1, 1] 到 [2, 2] 内的所有元素加 1。
第二次操作将子矩阵 [2, 2] 到 [3, 3] 内的所有元素加 1。
最终输出每个元素的值是否为奇数。

通过以上思路和逻辑，代码能够高效地处理多次区间更新操作，并快速查询每个元素的值是否为奇数。

重点：

还原数组 a[][] 的方式是基于 二维前缀和 的原理。需要从 差分数组 和 前缀和 的基本概念入手，逐步推导这个公式。

1. 差分数组的作用

差分数组 d[][] 的作用是高效记录区间更新操作。对于二维数组，差分数组的更新规则如下：

对于一个子矩阵 [x1, y1] 到 [x2, y2] 的区间加 1 操作，这些更新操作的作用是：
d[x1][y1]++：表示从 (x1, y1) 开始的区域增加 1。
d[x1][y2 + 1]--：表示从 (x1, y2 + 1) 开始的区域减少 1。
d[x2 + 1][y1]--：表示从 (x2 + 1, y1) 开始的区域减少 1。
d[x2 + 1][y2 + 1]++：表示从 (x2 + 1, y2 + 1) 开始的区域增加 1。

通过这些操作，差分数组 d[][] 记录了每个位置的增量。

2. 前缀和的作用

前缀和的作用是通过累加差分数组 d[][] 来还原原数组 a[][]。对于二维数组，前缀和的计算公式为：

a[i][j]=d[i][j]+a[i−1][j]+a[i][j−1]−a[i−1][j−1]

这个公式的含义是：

a[i][j] 表示 (i, j) 位置的值。
d[i][j] 是 (i, j) 位置的增量。
a[i - 1][j] 是 (i - 1, j) 位置的值，表示上方的前缀和。
a[i][j - 1] 是 (i, j - 1) 位置的值，表示左方的前缀和。
a[i - 1][j - 1] 是 (i - 1, j - 1) 位置的值，表示左上角的前缀和。

通过这个公式，我们可以将差分数组 d[][] 的增量信息累加到原数组 a[][] 中。

3. 公式的推导

为什么这个公式是正确的？我们可以从 容斥原理 的角度来理解。

目标：计算 (i, j) 位置的值 a[i][j]。
增量来源：
- d[i][j]：直接贡献给 (i, j) 的增量。
- a[i - 1][j]：上方的前缀和，包含了 (i - 1, j) 及其左侧的所有增量。
- a[i][j - 1]：左方的前缀和，包含了 (i, j - 1) 及其上方的所有增量。
- a[i - 1][j - 1]：左上角的前缀和，被 a[i - 1][j] 和 a[i][j - 1] 重复计算了，需要减去。

因此，公式可以理解为：

a[i][j]=直接增量+上方前缀和+左方前缀和−左上角前缀和a[i][j]=直接增量+上方前缀和+左方前缀和−左上角前缀和

4. 举例说明

假设有一个 3x3 的矩阵，初始时所有元素为 0。我们进行一次区间加 1 操作，范围为 [1, 1] 到 [2, 2]。

更新差分数组

d[1][1]++
d[1][3]--
d[3][1]--
d[3][3]++

差分数组 d[][] 的值如下：

d[1][1] = 1
d[1][3] = -1
d[3][1] = -1
d[3][3] = 1

还原原数组

通过前缀和公式计算 a[][]：

a[1][1] = d[1][1] + a[0][1] + a[1][0] - a[0][0] = 1 + 0 + 0 - 0 = 1
a[1][2] = d[1][2] + a[0][2] + a[1][1] - a[0][1] = 0 + 0 + 1 - 0 = 1
a[2][1] = d[2][1] + a[1][1] + a[2][0] - a[1][0] = 0 + 1 + 0 - 0 = 1
a[2][2] = d[2][2] + a[1][2] + a[2][1] - a[1][1] = 0 + 1 + 1 - 1 = 1

最终原数组 a[][] 的值如下：

1 1 0
1 1 0
0 0 0

5. 总结

还原数组 a[][] 的公式：

a[i][j]=d[i][j]+a[i−1][j]+a[i][j−1]−a[i−1][j−1]

是基于 二维前缀和 和 容斥原理 的推导。通过这个公式，我们可以高效地将差分数组 d[][] 的增量信息累加到原数组 a[][] 中，从而还原出每个位置的值。

四、 1.灵能传输 - 蓝桥云课

算法代码：

#include <iostream>
#include <algorithm>
using namespace std;#define ll long long
#define N 300005ll sum[N], path[N];  // sum[] 存储前缀和，path[] 存储最终调整后的前缀和数组
bool mark[N];        // mark[] 用于标记某个前缀和是否已经被访问int main()
{int n;cin >> n;  // 读取询问组数while(n--){int m;cin >> m;  // 读取每组询问的高阶圣堂武士数量fill_n(mark, N, false);  // 初始化 mark[] 数组为 falsefill_n(sum, N, 0);       // 初始化 sum[] 数组为 0fill_n(path, N, 0);      // 初始化 path[] 数组为 0// 计算前缀和数组 sum[]for(int i = 1; i <= m; i++){cin >> sum[i];  // 读取灵能值sum[i] += sum[i - 1];  // 计算前缀和}ll begin = sum[0], end = sum[m];  // 记录前缀和数组的首尾项if(begin > end){swap(begin, end);  // 如果 begin > end，交换它们的值}sort(sum, sum + m + 1);  // 对前缀和数组进行排序// 找到排序后 begin 和 end 的下标for(int i = 0; i <= m; i++){if(sum[i] == begin){begin = i;  // 找到 begin 的下标break;}}for(int i = m; i >= 0; i--){if(sum[i] == end){end = i;  // 找到 end 的下标break;}}int left = 0, right = m;  // left 和 right 分别指向 path[] 的开头和末尾// 从 begin 开始，每隔一个元素赋值到 path[] 的开头for(int i = begin; i >= 0; i -= 2){path[left++] = sum[i];  // 赋值到 path[] 的开头mark[i] = true;         // 标记该前缀和已被访问}// 从 end 开始，每隔一个元素赋值到 path[] 的末尾for(int i = end; i <= m; i += 2){path[right--] = sum[i];  // 赋值到 path[] 的末尾mark[i] = true;         // 标记该前缀和已被访问}// 将未访问的前缀和按顺序赋值到 path[] 的中间for(int i = 0; i <= m; i++){if(!mark[i]){path[left++] = sum[i];  // 赋值到 path[] 的中间}}ll answer = 0;  // 初始化不稳定度为 0// 计算 path[] 中相邻元素的差值的最大值for(int i = 1; i <= m; i++){answer = max(answer, abs(path[i] - path[i - 1]));  // 更新不稳定度}cout << answer << endl;  // 输出每组询问的不稳定度}return 0;
}

这段代码的主要目的是解决一个与 前缀和 和 不稳定度 相关的问题。以下是代码的详细思路和解释：

代码思路

问题描述：
- 给定一个长度为 m 的数组，表示高阶圣堂武士的灵能值。
- 通过调整数组的顺序，使得调整后的数组的前缀和数组的 不稳定度 最小。
- 不稳定度定义为前缀和数组中相邻元素的差值的最大值。
算法选择：
- 使用 前缀和 和排序来构造满足条件的前缀和数组。
- 通过 贪心策略 构造路径，使得相邻元素的差值尽可能小。
代码结构：
- 读取输入数据，计算前缀和数组。
- 对前缀和数组进行排序。
- 构造满足条件的前缀和数组 path[]。
- 计算不稳定度并输出结果。

代码详解

1. 预处理

int n;
cin >> n;  // 读取询问组数
while(n--){int m;cin >> m;  // 读取每组询问的高阶圣堂武士数量fill_n(mark, N, false);  // 初始化 mark[] 数组为 falsefill_n(sum, N, 0);       // 初始化 sum[] 数组为 0fill_n(path, N, 0);      // 初始化 path[] 数组为 0

读取询问组数 n 和每组询问的数组长度 m。
初始化 mark[]、sum[] 和 path[] 数组。

2. 计算前缀和数组

for(int i = 1; i <= m; i++){cin >> sum[i];  // 读取灵能值sum[i] += sum[i - 1];  // 计算前缀和
}

计算数组的前缀和 sum[]，其中 sum[i] 表示数组前 i 个元素的和。

3. 记录首尾项并排序

ll begin = sum[0], end = sum[m];  // 记录前缀和数组的首尾项
if(begin > end){swap(begin, end);  // 如果 begin > end，交换它们的值
}sort(sum, sum + m + 1);  // 对前缀和数组进行排序

记录前缀和数组的首项 sum[0] 和尾项 sum[m]。
如果 begin > end，交换它们的值。
对前缀和数组 sum[] 进行排序。

4. 找到首尾项的下标

for(int i = 0; i <= m; i++){if(sum[i] == begin){begin = i;  // 找到 begin 的下标break;}
}
for(int i = m; i >= 0; i--){if(sum[i] == end){end = i;  // 找到 end 的下标break;}
}

在排序后的 sum[] 中找到 begin 和 end 的下标。

5. 构造 path[] 数组

int left = 0, right = m;  // left 和 right 分别指向 path[] 的开头和末尾// 从 begin 开始，每隔一个元素赋值到 path[] 的开头
for(int i = begin; i >= 0; i -= 2){path[left++] = sum[i];  // 赋值到 path[] 的开头mark[i] = true;         // 标记该前缀和已被访问
}// 从 end 开始，每隔一个元素赋值到 path[] 的末尾
for(int i = end; i <= m; i += 2){path[right--] = sum[i];  // 赋值到 path[] 的末尾mark[i] = true;         // 标记该前缀和已被访问
}// 将未访问的前缀和按顺序赋值到 path[] 的中间
for(int i = 0; i <= m; i++){if(!mark[i]){path[left++] = sum[i];  // 赋值到 path[] 的中间}
}

使用 贪心策略 构造 path[] 数组：
- 从 begin 开始，每隔一个元素赋值到 path[] 的开头。
- 从 end 开始，每隔一个元素赋值到 path[] 的末尾。
- 将未访问的前缀和按顺序赋值到 path[] 的中间。

6. 计算不稳定度

ll answer = 0;  // 初始化不稳定度为 0// 计算 path[] 中相邻元素的差值的最大值
for(int i = 1; i <= m; i++){answer = max(answer, abs(path[i] - path[i - 1]));  // 更新不稳定度
}cout << answer << endl;  // 输出每组询问的不稳定度