【一百零四】【算法分析与设计】【模板】二维差分,2132. 用邮票贴满网格图,LCP 74. 最强祝福力场,二位差分,差分思想,记录变化值,离散化技巧

【模板】二维差分

描述

给你一个n行m列的矩阵，下标从1开始。

接下来有q次操作，每次操作输入5个参数x1, y1, x2, y2, k

表示把以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k，

请输出操作后的矩阵。

输入描述：

第一行包含三个整数n,m,q.

接下来n行，每行m个整数，代表矩阵的元素

接下来q行，每行5个整数x1, y1, x2, y2, k，分别代表这次操作的参数

$1\le n,m \le 1000$

$1\le q \le 10^5$

$1\le x1 \le x2 \le n$

$1\le y1 \le y2 \le m$

$-10^9 \le 矩阵中的元素 \le 10^9$

输出描述：

输出n行，每行m个数，每个数用空格分开，表示这个矩阵。

示例1

输入：

2 3 4

1 2 3

4 5 6

1 1 2 2 3

1 2 2 3 -1

1 1 1 3 4

1 1 2 1 1

复制

输出：

9 8 6

8 7 5

复制

差分思想,存储影响的量,和消除影响的量.

例如我在A区域全部加上k值.

如果原本的值全是0,那么结果应该如下图所示.

此时我们只需要存储一部分值即可,如下图所示.

我们对每一行求前缀和,求出来的结果就是我们想要的答案.

可以理解为,从某个位置开始应该影响,影响的值是K,从某个位置开始影响,影响的值是-K.

前面是影响的值,后面是消除影响的值.

也可以理解为原先有很多的重复的数据,而我们只存储改变量,记录从什么时候开始改变了,改变了多少.

接着我们发现上面的数据仍然有许多的重复的数据,一列的K,和一列的-K.

因此我们只需要存储一部分数据,如下图所示.

对上面的数据先按照列进行求前缀和,再对列的前缀和求行的前缀和,求出来的就是答案.

上面的方法需要遍历两遍diff数组,当然更加常见的是只遍历一遍的diff数组,这个也是可以做到的.

同样是由这个数据出发,我们需要得到每个数据的列前缀和的行前缀和.

可以利用一点点动态规划的思想,假设我们要得到(i,j)位置的列前缀和的行前缀和值,能不能由其他位置的列前缀和的行前缀和值转移得到?

我们可以先求当前位置的列前缀和,那么就需要用到上一行的列前缀和加上当前元素值.

上一行的列前缀和等于上一行的列前缀和的行前缀和减去上一行上一列的列前缀和的行前缀和.

可以想象我们有一个矩阵全部存储的是列前缀和值.如下图所示.

假设我要求B位置的值,只需要用蓝色区域前缀和减去绿色区域前缀和即可.

也就是列前缀和的行前缀和相减.

用公式来表示,diff[i-1][j]-diff[i-1][j-1]+g[i][j]这样得到的就是当前位置的列前缀和.

然后再对当前位置列前缀和求行前缀和,只需要加上上一列的列前缀和的行前缀和即可.

用公式来表示,diff[i-1][j]-diff[i-1][j-1]+g[i][j]+diff[i][j-1]这样计算得到的就是当前位置的列前缀和的行前缀和.

填写(i,j)位置需要用到i-1,j-1位置的状态,所以填表顺序i,j从小到大即可.

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

#define int long long
#define endl '\n'
#define fast() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

#define p pair<int,int>
#define ff first
#define ss second
#define _(i,a,b) for(int i=a;i<=b;i++)
#define _1(i,a,b) for(int i=a;i>=b;i--)

int n, m, q;
vector<vector<int>>g;  // 用于存储矩阵元素的二维向量
struct node {
    int x1, y1;
    int x2, y2;
    int k;
};
vector<node>readd;  // 存储每次操作的参数
vector<vector<int>>diff;  // 存储每次操作导致的变化量

void sett(int x1, int y1, int x2, int y2, int k) {
    diff[x1][y1] += k;  // 左上角元素增加k
    diff[x1][y2 + 1] -= k;  // 右上角元素增加k
    diff[x2 + 1][y1] -= k;  // 左下角元素增加k
    diff[x2 + 1][y2 + 1] += k;  // 右下角元素增加k
}

void solve() {
    for (auto& xx : readd) {
        sett(xx.x1, xx.y1, xx.x2, xx.y2, xx.k);  // 对每次操作进行处理
    }

    _(j, 1, m) {  // 对每列进行处理
        _(i, 1, n) {  // 对每行进行处理
            diff[i][j] = diff[i - 1][j] + diff[i][j];  // 更新当前元素的值
        }
    }

    _(i, 1, n) {
        _(j, 1, m) {
            diff[i][j] = diff[i][j - 1] + diff[i][j];  
            g[i][j] += diff[i][j];  // 更新矩阵元素的值
            cout << g[i][j] << " ";  // 输出当前元素值
        }
        cout << endl;  // 换行
    }

}

signed main() {
    fast();  // 快速IO

    cin >> n >> m >> q;  // 输入矩阵的行数、列数和操作次数
    readd.clear();  // 清空操作参数
    diff.assign(n + 5, vector<int>(m + 5, 0));  // 初始化变化量向量
    g.assign(n + 5, vector<int>(m + 5, 0));  // 初始化矩阵向量
    _(i, 1, n) {
        _(j, 1, m) {
            cin >> g[i][j];  // 输入矩阵元素
        }
    }

    _(i, 1, q) {
        node tt;
        cin >> tt.x1 >> tt.y1 >> tt.x2 >> tt.y2 >> tt.k;  // 输入每次操作的参数
        readd.push_back(tt);  // 存储操作参数
    }

    solve();  // 解决问题
}

2132. 用邮票贴满网格图

给你一个 m x n 的二进制矩阵 grid ，每个格子要么为 0 （空）要么为 1 （被占据）。

给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中，且满足以下限制和要求：

覆盖所有空格子。

不覆盖任何 被占据 的格子。

我们可以放入任意数目的邮票。

邮票可以相互有重叠部分。

邮票不允许旋转。

邮票必须完全在矩阵内。

如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false 。

示例 1：

输入： grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3 输出： true 解释： 我们放入两个有重叠部分的邮票（图中标号为 1 和 2），它们能覆盖所有与空格子。

示例 2：

输入： grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 输出： false 解释： 没办法放入邮票覆盖所有的空格子，且邮票不超出网格图以外。

提示：

m == grid.length

n == grid[r].length

1 <= m, n <= 10(5)

1 <= m * n <= 2 * 10(5)

grid[r][c] 要么是 0 ，要么是 1 。

1 <= stampHeight, stampWidth <= 10(5)

1表示的是不能放邮票的位置,0表示可以放邮票的位置,而邮票的长宽是固定的,而且邮票不能旋转.

那么可以遍历所有的点,找到此时对于的邮票的左上角点x1,y1,右下角点x2,y2.

计算这个矩形区域里面的累加和,如果累加和是0说明可以放邮票,如果累加和不为0说明不能放邮票.

题目要求我们判断能不能将所有0位置都覆盖上邮票.我们不能,放置邮票之后修改0为1,因为邮票是可以叠在一起的,而是要记录所有盖上邮票的位置,然后比对所有0的位置是否被邮票覆盖.

因此我们可以在放置邮票的位置全部累加1,这个累加值是在一个新的数组上进行,然后遍历所有位置,如果是0就看对应位置是否为0,不为0说明被邮票覆盖了,为0说明没有被覆盖过.

而对一个二维区域全部累加1就可以用差分思维.

class Solution {
public:
    vector<vector<int>> g;    // 二进制矩阵
    int height, width;        // 邮票的高度和宽度
    bool flag;                // 是否能成功放置邮票的标志
    vector<vector<int>> prev; // 原始矩阵的前缀和
    int n, m;                 // 矩阵的行数和列数
    vector<vector<int>> diff; // 差分数组，用于辅助计算

    // 更新差分数组
    void sett(int x1, int y1, int x2, int y2) {
        diff[x1][y1] += 1;
        diff[x1][y2 + 1] -= 1;
        diff[x2 + 1][y1] -= 1;
        diff[x2 + 1][y2 + 1] += 1;
    }

    // 获取差分数组区间和
    int gett(int x1, int y1, int x2, int y2) {
        return prev[x2][y2] - (x1 - 1 >= 0 ? prev[x1 - 1][y2] : 0) -
               (y1 - 1 >= 0 ? prev[x2][y1 - 1] : 0) +
               (x1 - 1 >= 0 && y1 - 1 >= 0 ? prev[x1 - 1][y1 - 1] : 0);
    }

    // 解决问题的函数
    void solve() {
        n = g.size();
        m = g[0].size();
        diff.assign(n + 5, vector<int>(m + 5, 0));
        prev = g;
        flag = false;

        // 计算原始矩阵的前缀和
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                prev[i][j] =
                    (i - 1 >= 0 ? prev[i - 1][j] : 0) +
                    (j - 1 >= 0 ? prev[i][j - 1] : 0) -
                    (i - 1 >= 0 && j - 1 >= 0 ? prev[i - 1][j - 1] : 0) +
                    prev[i][j];
            }
        }

        // 尝试在所有可能的位置放置邮票
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int x1 = i, y1 = j;
                int x2 = i + height - 1, y2 = j + width - 1;
                if(y2>=m)break;
                if(x2>=n)goto f1;
                if (gett(x1, y1, x2, y2) == 0) {
                    sett(x1, y1, x2, y2);
                }
            }
        }
        f1:

        // 计算差分数组的行累加和
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                diff[i][j] += (i - 1 >= 0 ? diff[i - 1][j] : 0);
            }
        }

        // 计算差分数组的列累加和
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                diff[i][j] += (j - 1 >= 0 ? diff[i][j - 1] : 0);
            }
        }

        // 检查是否所有空格子都被覆盖
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 0) {
                    if (diff[i][j] == 0) {
                        flag = false;
                        return;
                    }
                }
            }
        }

        flag = true;
    }

    // 判断是否可以成功放置邮票的函数
    bool possibleToStamp(vector<vector<int>>& _grid, int _stampHeight,
                         int _stampWidth) {
        g = _grid, height = _stampHeight, width = _stampWidth;
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();  // 解决问题
        return flag;  // 返回结果
    }
};

LCP 74. 最强祝福力场

小扣在探索丛林的过程中，无意间发现了传说中“落寞的黄金之都”。而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场。经过不断的勘测记录，小扣将所有力场的分布都记录了下来。forceField[i] = [x,y,side] 表示第 i 片力场将覆盖以坐标 (x,y) 为中心，边长为 side 的正方形区域。

若任意一点的 力场强度 等于覆盖该点的力场数量，请求出在这片地带中 力场强度 最强处的 力场强度。

注意：

力场范围的边缘同样被力场覆盖。

示例 1：

输入： forceField = [[0,0,1],[1,0,1]]

输出：2

解释：如图所示，（0.5, 0) 处力场强度最强为 2，（0.5，-0.5）处力场强度同样是 2。

示例 2：

输入： forceField = [[4,4,6],[7,5,3],[1,6,2],[5,6,3]]

输出：3

解释：如下图所示， forceField[0]、forceField[1]、forceField[3] 重叠的区域力场强度最大，返回 3

提示：

1 <= forceField.length <= 100

forceField[i].length == 3

0 <= forceField[i][0], forceField[i][1] <= 10^9

1 <= forceField[i][2] <= 10^9

每一个辐力区域的辐力值都是1,这些辐力值都是叠加效果.

我们要做的是将每一个矩形区域累加1,然后计算矩形区域最大的值是多少.

重要的并不是矩形区域累加1,因为这个操作用差分就可以完成,重要的是这些点并不能用区域很好的表示,这里就需要用到离散化的技巧.

假设我们需要用到的点是1,2,6,8,12,1000,正常来说为了表示这些点,需要开辟至少1000大小空间的数组.

但是我们让上面的每一个需要用到的数依次映射012345,这样只需要用到5个数.

关键点是我们需要用到的数必须排序好了.

依次我们可以用map容器,先存储所有需要用到的点放到里面,但是second先不修改.

当我们将所有需要用到的点都放进去了之后,再遍历map依次赋值second为0,1,2…

这样我们只需要关心映射之后的下标值即可,因为这道题目不关心下标,所以也不需要建立0,1,2…映射原下标的操作.

#define LL long long

class Solution {
public:

    vector<vector<int>> readd; // 记录力场的分布
    map<LL, LL> x_map;       // 横坐标映射
    LL n, m;                  // x_map和y_map的大小
    map<LL, LL> y_map;       // 纵坐标映射
    LL ret;                   // 最终结果
    vector<vector<LL>> diff; // 差分数组，用于计算力场强度

    // 更新差分数组
    void sett(LL x1, LL y1, LL x2, LL y2) {
        diff[x1][y1] += 1;
        diff[x1][y2 + 1] -= 1;
        diff[x2 + 1][y1] -= 1;
        diff[x2 + 1][y2 + 1] += 1;
    }

    // 解决问题
    void solve() {
        n = 0, m = 0;  // 初始化坐标映射大小
        ret = 0;  // 初始化最终结果为0
        x_map.clear(), y_map.clear();  // 清空坐标映射

        // 构建坐标映射
        for (auto& xx : readd) {
            x_map[2LL * xx[0] - xx[2]];
            x_map[2LL * xx[0] + xx[2]];
            y_map[2LL * xx[1] - xx[2]];
            y_map[2LL * xx[1] + xx[2]];
        }

        LL index = 0;
        for (auto& xx : x_map) {
            xx.second = index++;
        }
        n = index;

        index = 0;
        for (auto& xx : y_map) {
            xx.second = index++;
        }
        m = index;

        // 初始化差分数组大小
        diff.assign(n + 5, vector<LL>(m + 5, 0));

        // 计算力场覆盖情况
        for (auto& xx : readd) {
            LL x1 = x_map[2LL * xx[0] - xx[2]];
            LL x2 = x_map[2LL * xx[0] + xx[2]];
            LL y1 = y_map[2LL * xx[1] - xx[2]];
            LL y2 = y_map[2LL * xx[1] + xx[2]];
            sett(x1, y1, x2, y2);
        }

        // 计算力场强度
        for (LL j = 0; j < m; j++) {
            for (LL i = 0; i < n; i++) {
                diff[i][j] += (i - 1 >= 0 ? diff[i - 1][j] : 0);
            }
        }
        for (LL i = 0; i < n; i++) {
            for (LL j = 0; j < m; j++) {
                diff[i][j] += (j - 1 >= 0 ? diff[i][j - 1] : 0);
                ret = max(ret, diff[i][j]);  // 更新最大力场强度
            }
        }
    }

    // 计算最大力场强度的函数
    int fieldOfGreatestBlessing(vector<vector<int>>& _forceField) {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        readd = _forceField;  // 获取力场数据
        solve();  // 解决问题
        return ret;  // 返回结果
    }
};