蓝桥杯第九讲--差分【例/习题】

前言差分

题目要求思路分析代码 差分矩阵

题目要求思路分析代码

蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第九讲：差分【例/习题】

本篇博客所包含习题有：
差分
差分矩阵

有关差分的内容细致讲解见博文：差分
有关差分的模板见博文：差分算法模板

博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！

题目描述：

输入一个长度为 n n n 的整数序列。

接下来输入 m m m 个操作，每个操作包含三个整数 l , r , c l,r,c l,r,c，表示将序列中 [ l , r ] [l,r] [l,r] 之间的每个数加上 c c c。

请你输出进行完所有操作后的序列。

输入格式：

第一行包含两个整数 n n n 和 m m m。

第二行包含 n n n 个整数，表示整数序列。

接下来 m m m 行，每行包含三个整数 l ， r ， c l，r，c l，r，c，表示一个操作。

输出格式：

共一行，包含 n n n 个整数，表示最终序列。

数据范围：

1 ≤ n , m ≤ 100000 , 1≤n,m≤100000, 1≤n,m≤100000,
1 ≤ l ≤ r ≤ n , 1≤l≤r≤n, 1≤l≤r≤n,
− 1000 ≤ c ≤ 1000 , −1000≤c≤1000, −1000≤c≤1000,
− 1000 ≤ −1000≤ −1000≤ 整数序列中元素的值 ≤ 1000 ≤1000 ≤1000

输入样例：

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例：

3 4 5 3 4 2

一维差分的模板题，对于差分你可以理解成为前缀和的逆运算，差分数组的构造方法为：

s数组是差分数组,a数组是原数组
s[0] = 0, a[0] = 0;
s[1] = a[1] - a[0];
s[2] = a[2] - a[1];
...
s[n] = a[n] - a[n - 1];

令 a a a数组在 [ l , r ] [l,r] [l,r] 的区间内加上一个数 c c c 可以用差分的思维：

s[l] += c;
s[r + 1] -= c;

然后对差分数组做一遍前缀和即可。

#include 
#include 
#include 

using namespace std;

const int N = 100010;

int a[N], s[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    // 处理差分数组
    for (int i = 1; i <= n; i ++ ) s[i] = a[i] - a[i - 1];
    
    while (m -- )
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        s[l] += c, s[r + 1] -= c;
    }
    
    for (int i = 1; i <= n; i ++ ) 
    {
        s[i] += s[i - 1];
        printf("%d ", s[i]);
    }
    
    return 0;
}

题目描述：

输入一个 n n n 行 m m m 列的整数矩阵，再输入 q q q 个操作，每个操作包含五个整数 x 1 , y 1 , x 2 , y 2 , c x_1,y_1,x_2,y_2,c x1​,y1​,x2​,y2​,c，其中 ( x 1 , y 1 ) (x_1,y_1) (x1​,y1​) 和 ( x 2 , y 2 ) (x_2,y_2) (x2​,y2​) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c c c。

请你将进行完所有操作后的矩阵输出。

输入格式：

第一行包含整数 n , m , q n,m,q n,m,q。

接下来 n n n 行，每行包含 m m m 个整数，表示整数矩阵。

接下来 q q q 行，每行包含 5 5 5 个整数 x 1 , y 1 , x 2 , y 2 , c x_1,y_1,x_2,y_2,c x1​,y1​,x2​,y2​,c，表示一个操作。

输出格式：

共 n n n 行，每行 m m m 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围：

1 ≤ n , m ≤ 1000 , 1≤n,m≤1000, 1≤n,m≤1000,
1 ≤ q ≤ 100000 , 1≤q≤100000, 1≤q≤100000,
1 ≤ x 1 ≤ x 2 ≤ n , 1≤x_1≤x_2≤n, 1≤x1​≤x2​≤n,
1 ≤ y 1 ≤ y 2 ≤ m , 1≤y_1≤y_2≤m, 1≤y1​≤y2​≤m,
− 1000 ≤ c ≤ 1000 , −1000≤c≤1000, −1000≤c≤1000,
− 1000 ≤ −1000≤ −1000≤ 矩阵内元素的值 ≤ 1000 ≤1000 ≤1000

输入样例：

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

输出样例：

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

对于二维差分数组，你可以这么去理解：如果前缀和的二维矩阵上的某一点是影响从矩阵左上角到该点内的数，那么差分数组矩阵就是影响从这一点到矩阵右下角，往 a a a数组（二维） ( x 1 , y 1 ) (x_1,y_1) (x1​,y1​) 【左上角】和 ( x 2 , y 2 ) (x_2,y_2) (x2​,y2​) 【右下角】的矩阵内加上一个数 c c c 可用差分：

s[x1][y1] += c;
s[x2 + 1][y1] -= c;
s[x1][y2 + 1] -= c;
s[x2 + 1][y2 + 1] += c;

然后再计算一遍前缀和数组，即可得到结果，注意我们的前缀和模板应该是：

s[i, j] = s[i, j - 1] + s[i - 1, j] - s[i - 1, j - 1] + a[i, j];

但此时的 s [ i , j ] s[i, j] s[i,j] 其实就是一个值，即也为 a [ i , j ] a[i,j] a[i,j]，故把差分数组变为前缀和数组为：

s[i][j] += s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1];

#include 
#include 
#include 

using namespace std;

const int N = 1010;

int a[N][N], s[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    s[x1][y1] += c;
    s[x2 + 1][y1] -= c;
    s[x1][y2 + 1] -= c;
    s[x2 + 1][y2 + 1] += c;
}

int main()
{
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ ) 
            scanf("%d", &a[i][j]);
    // 处理差分数组
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ )
            insert(i, j, i, j, a[i][j]);
            
    while (q -- )
    {
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    // 计算前缀和数组
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ ) 
            s[i][j] += s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1];
            
    for (int i = 1; i <= n; i ++ ) 
    {
        for (int j = 1; j <= m; j ++ ) 
            printf("%d ", s[i][j]);
        puts("");
    }
    
    return 0;   
}