前缀和与差分 | 基本算法

参考《算法竞赛进阶指南》、AcWing题库

前缀和与差分

前缀和

对于一个给定的数列 $A$, 它的前缀和数列 $S$ 是通过递推能求出的基本信息之一:

$$S[i]=\sum_{j=1}^{i} A[j]$$

一个部分和, 即数列 $A$ 某个下标区间内的数的和, 可表示为前缀和相减的形式:

$$\operatorname{sum}(l, r)=\sum_{i=1}^{r} A[i]=S[r]-S[l-1]$$

在二维数组 (矩阵) 中, 可类似地求出二维前缀和, 进一步计算出二维部分和。

---

99. 激光炸弹

地图上有 $N$ 个目标，用整数 $X_{i}, Y_{i}$ 表示目标在地图上的位置，每个目标都有一个价值 $W_i$。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含 $R \times R$ 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 $x，y$ 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 $N$ 和 $R$，分别代表地图上的目标数目和正方形的边长，数据用空格隔开。

接下来 $N$ 行，每行输入一组数据，每组数据包括三个整数 $X_{i}, Y_{i}, W_{i}$，分别代表目标的 $x$ 坐标，$y$ 坐标和价值，数据用空格隔开。

输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

$0 \le R \le 10^9$
$0 < N \le 10000$,
$0 \le X_{i}, Y_{i} \le 5000$
$0 \le W_i \le 1000$

输入样例：

2 1
0 0 1
1 1 1 

输出样例：

1 

算法分析

因为 $X_{i}, Y_{i}$ 的值在 $0 \sim 5000$ 之间, 所以我们可以建立一个二维数组 $A$, 其中 $A[i, j]$ 就等于位置 $(i, j)$ 上的所有目标的价值之和。即对于每个目标, 令 $A\left[X_{i}, Y_{i}\right]+=W_{i}$ 。 接下来我们求出 $A$ 的二维前缀和 $S$, 即:

$$S[i, j]=\sum_{x=1}^{i} \sum_{y=1}^{j} A[x, y]$$

如下图所示, 我们再观察 $S[i, j], S[i-1, j], S[i, j-1], S[i-1, j-1]$ 的关系:

容易得到如下的递推式:

$$S[i, j]=S[i-1, j]+S[i, j-1]-S[i-1, j-1]+A[i, j]$$

同理, 对于任意一个边长为 $R$ 的正方形, 我们有:

$$\sum_{x=i-R+1}^{i} \sum_{y=j-R+1}^{j} A[x, y]=S[i, j]-S[i-R, j]-S[i, j-R]+S[i-R, j-R]$$

因此, 我们只需要 $O\left(N^{2}\right)$ 递推求出二维前缀和 $S$, 然后 $O\left(N^{2}\right)$ 枚举边长为 $R$ 的正方形的右下角坐标 $(i, j)$, 即可通过上式 $O(1)$ 计算出该正方形内所有目标的价值之和, 更新答案。上面给出的两个式子蕴含的思想其实就是 “容斥原理”。

值得一提的是, 上面我们把 $\left(X_{i}, Y_{i}\right)$ 作为一个 “格子”, 而原题中 $\left(X_{i}, Y_{i}\right)$ 是一个点, 并且正方形边上的目标不会被摧毀。实际上, 我们不妨认为这个点就处于 “格子” $\left(X_{i}, Y_{i}\right)$ 的中心位置, 格子的左上角坐标为 $\left(X_{i}-0.5, Y_{i}-0.5\right)$, 右下角坐标为 $\left(X_{i}+0.5, Y_{i}+0.5\right)$, 而正方形的右下角处于 “格线交点”上, 即一个值为 “ $\square .5$ ” 的坐标。这个转化与原问题是等价的。另外, 本题内存限制较为严格, 我们可以省略 $A$ 数组, 读入时直接向 $S$ 中累加。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5006;
int n, r, s[N][N];

int main() {
	memset(s, 0, sizeof(s));
	cin >> n >> r;
	while (n--) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		s[x][y] += z;
	}
	for (int i = 0; i <= 5000; i++)
		for (int j = 0; j <= 5000; j++)
			if (!i && !j) continue;
			else if (!i) s[i][j] += s[i][j-1];
			else if (!j) s[i][j] += s[i-1][j];
			else s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
	int ans = 0;
	if(r<5001){
		for (int i = r - 1; i <= 5000; i++)
			for (int j = r - 1; j <= 5000; j++)
				if (i == r - 1 && j == r - 1) ans = max(ans, s[i][j]);
				else if (i == r - 1) ans = max(ans, s[i][j] - s[i][j-r]);
				else if (j == r - 1) ans = max(ans, s[i][j] - s[i-r][j]);
				else ans = max(ans, s[i][j] - s[i-r][j] - s[i][j-r] + s[i-r][j-r]);
	}
	else{	//r>=5001，可以覆盖所有区域
		ans=s[5000][5000];
	}
	cout << ans << endl;
	return 0;
}

Solution

---

差分

对于一个给定的数列 $A$, 它的差分数列 $B$ 定义为:

$$B[1]=A[1], \quad B[i]=A[i]-A[i-1](2 \leq i \leq n)$$

容易发现, “前缀和”与 “差分” 是一对互逆运算, 差分序列 $B$ 的前缀和序列就是原序列 $A$, 前缀和序列 $S$ 的差分序列也是原序列 $A$ 。

把序列 $A$ 的区间 $[l, r]$ 加 $d$ (即把 $A_{l}, A_{l+1}, \cdots, A_{r}$ 都加上 $d$ ), 其差分序列 $B$ 的变化为 $B_{l}$ 加 $d, B_{r+1}$ 减 $d$, 其他位置不变。这有助于我们在很多题目中, 把原序列上的 “区间操作” 转化为差分序列上的 “单点操作” 进行计算, 降低求解难度。

在 数的直径与最近公共祖先 中, 我们还会继续探讨差分技巧在树上的应用。

---

100. 增减序列

给定一个长度为 $n$ 的数列 ${a_1,a_2,…,a_n}$，每次可以选择一个区间 $[l,r]$，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入格式

第一行输入正整数 $n$。

接下来 $n$ 行，每行输入一个整数，第 $i+1$ 行的整数代表 $a_i$。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

$0 < n \le 10^5$,
$0 \le a_i <2147483648$

输入样例：

4
1
1
2
2 

输出样例：

1
2 

算法分析

求出 $a$ 的差分序列 $b$, 其中 $b_{1}=a_{1}, b_{i}=a_{i}-a_{i-1}(2 \leq i \leq n)$ 。令 $b_{n+1}=0$ 。题目对序列 $a$ 的操作, 相当于每次可以选出 $b_{1}, b_{2}, \cdots, b_{n+1}$ 中的任意两个数, 一个加 1, 另一个减 1。目标是把 $b_{2}, b_{3}, \cdots, b_{n}$ 变为全零。最终得到的数列 $a$ 就是由 $n$ 个 $b_{1}$ 构成的。

从 $b_{1}, b_{2}, \cdots, b_{n+1}$ 中任选两个数的方法可分为四类:

1. 选 $b_{i}$ 和 $b_{j}$, 其中 $2 \leq i, j \leq n$ 。这种操作会改变 $b_{2}, b_{3}, \cdots, b_{n}$ 中两个数的值。应该在保证 $b_{i}$ 和 $b_{j}$ 一正一负的前提下, 尽量多地采取这种操作, 更快地接近目标。
2. 选 $b_{1}$ 和 $b_{j}$, 其中 $2 \leq j \leq n$ 。
3. 选 $b_{i}$ 和 $b_{n+1}$, 其中 $2 \leq i \leq n$ 。
4. 选 $b_{1}$ 和 $b_{n+1}$ 。这种情况没有意义, 因为它不会改变 $b_{2}, b_{3}, \cdots, b_{n}$ 的值, 相当于浪费了一次操作, 一定不是最优解。

设 $b_{2}, b_{3}, \cdots, b_{n}$ 中正数总和为 $p$, 负数总和的绝对值为 $q$ 。首先以正负数配对的方式尽量执行第 1 类操作, 可执行 $\min (p, q)$ 次。剩余 $|p-q|$ 个未配对, 每个可以选与 $b_{1}$ 或 $b_{n+1}$ 配对, 即执行第 2 或 3 类操作, 共需 $|p-q|$ 次。

综上所述, 最少操作次数为 $\min (p, q)+|p-q|=\max (p, q)$ 次。根据 $|p-q|$ 次第 2、3 类操作的选择情况, 能产生: $|p-q|+1$ 种不同的 $b_{1}$ 的值, 即最终得到的序列 $a$ 可能有 $|p-q|+1$ 种。

#include <cmath>
#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;
const int N = 100006;
ll a[N], b[N];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	b[1] = a[1];
	for (int i = 2; i <= n; i++) b[i] = a[i] - a[i-1];
	ll p = 0, q = 0;
	for (int i = 2; i <= n; i++)
		if (b[i] > 0) p += b[i];
		else if (b[i] < 0) q -= b[i];
	cout << max(p, q) << endl << abs(p - q) + 1 << endl;
	return 0;
}

Solution

---

101. 最高的牛

有 $N$ 头牛站成一行，被编队为 $1、2、3…N$，每头牛的身高都为整数。

当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。

现在，我们只知道其中最高的牛是第 $P$ 头，它的身高是 $H$ ，剩余牛的身高未知。

但是，我们还知道这群牛之中存在着 $M$ 对关系，每对关系都指明了某两头牛 $A$ 和 $B$ 可以相互看见。

求每头牛的身高的最大可能值是多少。

输入格式

第一行输入整数 $N, P, H, M$，数据用空格隔开。

接下来 $M$ 行，每行输出两个整数 $A$ 和 $B$ ，代表牛 $A$ 和牛 $B$ 可以相互看见，数据用空格隔开。

输出格式

一共输出 $N$ 行数据，每行输出一个整数。

第 $i$ 行输出的整数代表第 $i$ 头牛可能的最大身高。

数据范围

$1 \le N \le 10000$,
$1 \le H \le 1000000$,
$1 \le A,B \le 10000$,
$0 \le M \le 10000$

输入样例：

9 3 5 5
1 3
5 3
4 3
3 7
9 8 

输出样例：

5
4
5
3
4
4
5
5
5 

注意：

• 此题中给出的关系对可能存在重复

算法分析

题目中的 $M$ 对关系带给我们的信息实际上是牛之间身高的相对大小关系。具体来说, 我们建立一个数组 $C$, 数组中起初全为 0 。若一条关系指明 $A_{i}$ 和 $B_{i}$ 可以互相看见 (不妨设 $A_{i}<B_{i}$ ), 则把数组 $C$ 中下标为 $A_{i}+1$ 到 $B_{i}-1$ 的数都减去 1 , 意思是在 $A_{i}$ 和 $B_{i}$ 中间的牛, 身高至少要比它们小 1。因为第 $P$ 头牛是最高的, 所以最终 $C[P]$ 一定为 0 。其他的牛与第 $P$ 头牛的身高差距就体现在数组 $C$ 中。换言之, 最后第 $i$ 头牛的身高就等于 $H+C[i]$ 。

如果我们朴素执行把数组 $C$ 中下标为 $A_{i}+1$ 到 $B_{i}-1$ 的数都减去 1 的操作, 那么整个算法的时间复杂度为 $O(N M)$, 复杂度过高。一个简单而高效的做法是, 额外建立一个数组 $D$, 对于每对 $A_{i}$ 和 $B_{i}$, 令 $D\left[A_{i}+1\right]$ 减去 $1, D\left[B_{i}\right]$ 加上 1 。其含义是：“身高减小1”的影响从 $A_{i}+1$ 开始, 持续到 $B_{i}-1$, 在 $B_{i}$ 结束。最后, $C$ 就等于 $D$ 的前缀和, 即 $C[i]=\sum_{j=1}^{i} D[j]$, 如下图所示。

上述优化后的算法把对一个区间的操作转化为左、右两个端点上的操作, 再通过前缀和得到原问题的解。这种思想很常用, 我们在后面还会多次遇到。该算法的时间复杂度为 $\mathrm{O}(N+M)$ 。

值得提醒的是, 在本题的数据中, 一条关系 $\left(A_{i}, B_{i}\right)$ 可能会输入多次, 要注意检查, 对于重复的关系, 只在第一次出现时执行相关操作即可。

#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
map<pair<int, int>, bool> v;
const int N = 10006;
int s[N];

int main() {
    int n, p, h, t;
    cin >> n >> p >> h >> t;
    memset(s, 0, sizeof(s));
    while (t--) {
        int a, b;
        scanf("%d %d", &a, &b);
        if (a > b) swap(a, b);
        if (v[make_pair(a, b)]) continue;
        s[a+1]--;
        s[b]++;
        v[make_pair(a, b)] = 1;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += s[i];
        printf("%d\n", h + ans);
    }
    return 0;
}

Solution

---