《算法竞赛进阶指南》0x03 前缀和与差分

前缀和基础概念

对于一个给定的数列

，它的前缀和数列

是通过递推能求出的基本信息之一：

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

前缀和的作用

一个部分和，即数列

某个下标区间内的数的和，可表示为前缀和相减的形式

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

对于多维空间，同样可以定义前缀和，求部分和配合 容斥原理 即可实现

具体“容斥原理”会在数论章节讲解

例如 二维前缀和：

[ begin{aligned} S[i, j] &= S[i - 1, j] S[i, j - 1] - S[i - 1, j - 1] A[i, j] \ mathrm{sum}(x_1,y_1,x_2,y_2) &= S[x_2, y_2] - S[x_2, y_1 - 1] - S[x_1 - 1, y_2] S[x_1 - 1, y_1 - 1] end{aligned} ]

差分基础概念

对于一个给定的数列

，它的差分数列

定义为：

[ B[1] = A[1], ~ B[i] = A[i] - A[i - 1] ~ (2 le i le n) ]

差分的作用

“前缀和” 与 “差分” 互为逆运算：

差分序列

的前缀和序列就是原序列

；

前缀和序列

的差分序列也是原序列

；

把序列

的区间

[l,r]

加

（即把

A_{l},A_{l 1},cdots,A_{r}

都加上

），其差分序列

的变化为：

[ B[l] = d, ~ B[r 1] -= d ]

这有助于我们把原序列的 “区间操作” 转化为差分序列上的 “单点操作” 进行计算，从而降低求解难度

差分也可以在树上进行运用，会在图的章节进行讲解

习题

激光炸弹

题目描述

地图上有

个目标，用整数

X_i,Y_i

表示目标在地图上的位置，每个目标都有一个价值

W_i

。

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

现在有一种新型的激光炸弹，可以摧毁一个包含

R×R

个位置的正方形内的所有目标。

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

，

轴平行。

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

输入格式

第一行输入正整数

和

，分别代表地图上的目标数目和正方形的边长，数据用空格隔开。

接下来

行，每行输入一组数据，每组数据包括三个整数

X_i

Y_i

W_i

，分别代表目标的

坐标，

坐标和价值，数据用空格隔开。

输出格式

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

数据范围

0≤R≤10^9

0<N≤10000

0≤X_i,Y_i≤5000

0≤W_i≤1000

输入样例：

代码语言：javascript复制

2 1
0 0 1
1 1 1

输出样例：

代码语言：javascript复制

解析

二维前缀和

值得注意的一点，虽然“目标”位于网格线的交点，而我们的前缀和是以方格为单位累加的

因此我们不妨把“目标”统一偏移到网格的方格中：

(x,y) rightarrow (x 0.5, y 0.5)

且偏移后，新问题与原问题等价，并且新边界变得更好处理

代码语言：javascript复制

for (int i = 1; i < N; i    )
    for (int j = 1; j < N; j    )
        s[i][j]  = s[i - 1][j]   s[i][j - 1] - s[i - 1][j - 1];
for (int i = m; i < N; i    )
    for (int j = m; j < N; j    )
        res = max(res, s[i][j] - s[i - m][j] - s[i][j - m]   s[i - m][j - m]);

增减序列

题目描述

给定一个长度为

的数列

a_1,a_2,…,a_n

，每次可以选择一个区间

[l,r]

，使下标在这个区间内的数都加一或者都减一。

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

输入格式

第一行输入正整数

。

接下来

行，每行输入一个整数，第

i 1

行的整数代表

a_i

。

输出格式

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

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

数据范围

0<n≤10^5

0≤a_i<2147483648

输入样例：

代码语言：javascript复制

输出样例：

代码语言：javascript复制

1
2

解析

一维差分

区间修改，联想到用差分数组来维护，最终目标是使差分数组 除首元素外全为 0

每次修改一个区间，对于维护的差分数组变化情况分类：

(1 < l le r < n)

修改

[l, r]

：b[l] -- , b[r 1] 或 b[l] , b[r 1] --

修改

[1, r]

：b[1] -- , b[r 1] 或 b[1] , b[r 1] --

修改

[l, n]

：b[l] -- 或 b[l]

修改

[1, n]

：b[1] -- 或 b[1] （多余操作）

观察易得:

操作 4 是多余操作（不影响除首元素外元素值，相当于浪费一次操作，必然不是最优解）
操作 2 和操作 3 一次只能改变 1 个元素的值，操作 1 一次可以改变 2 个元素的值
操作 2 会改变首元素的值

为了让操作次数尽可能少，应尽可能使用操作 1

因此不妨设

b_2,...,b_n

中正数总和为

，

b_2,...,b_n

中负数总和为

然后让正负数配对，尽量执行操作 1，执行次数为

min(p, q)

剩余

|p - q|

个要么全是正数，要么全是负数，调用操作 2 或操作 3 都可，执行次数为

|p-q|

次

由于每次调用操作 2 时会改变一次首元素的值，因此首元素的可能值就有

|p - q| 1

种可能

因此最终答案为：

max(p, q)

和

|p - q| 1代码语言：javascript复制

long long 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;

最高的牛

题目描述

有

头牛站成一行，被编队为

1、2、3、…、N

，每头牛的身高都为整数。

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

现在，我们只知道其中最高的牛是第

头，它的身高是

，剩余牛的身高未知。

但是，我们还知道这群牛之中存在着

对关系，每对关系都指明了某两头牛

和

可以相互看见。

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

输入格式

第一行输入整数

N,P,H,M

，数据用空格隔开。

接下来

行，每行输出两个整数

和

，代表牛

和牛

可以相互看见，数据用空格隔开。

输出格式

一共输出

行数据，每行输出一个整数。

第

行输出的整数代表第

头牛可能的最大身高。

数据范围

1≤N≤10000

1≤H≤1000000

1≤A,B≤10000

0≤M≤10000

输入样例：

代码语言：javascript复制

输出样例：

代码语言：javascript复制

注意：此题中给出的关系对可能存在重复

解析

我们希望每对牛之间可以相互看见，并且每头牛的高度最高

一开始不妨假设所有牛的高度都是给出的最高牛的高度

要使第

头牛与第

头牛可以互相看见，那么只需让区间

[A 1, B - 1]

的牛高度减少 1 即可

可以直接用差分序列来维护原序列，则每次修改操作为：b[x 1] -- , b[y]

代码语言：javascript复制

int b[N];
set<PII> S;
int main()
{
    cin >> n >> p >> h >> m; b[1] = h;
    while (m -- )
    {
        int x, y;
        cin >> x >> y;
        if (x > y) swap(x, y);
        if (S.count({x, y})) continue;
        S.insert({x, y});
        b[x   1] -- , b[y]    ;
    }
    for (int i = 1; i <= n; i    )
    {
        b[i] = b[i - 1]   b[i];
        cout << b[i] << endl;
    }
    return 0;
}

地图

0 人点赞