基础：前缀和&差分 2021-07-04 算法 阅读次数：

工作后好久没发新文章了，有些文章其实是很久之前就写完了，但是一直没发。最近搬家了，开始了新的生活，先慢慢找回之前的节奏，把坑都填完

796. 子矩阵的和（模板题）

输入一个 行 列的整数矩阵，再输入 个询问，每个询问包含四个整数 ，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数 。

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

接下来 行，每行包含四个整数 ，表示一组询问。

输出格式

共 行，每行输出一个询问的结果。

数据范围

输入样例：

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例：

17
27
21

解法一

二维前缀和模板，一维的模板比较简单就不多写了

import java.util.*;
import java.io.*;

class Main {

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int N = in[0], M = in[1], Q = in[2];
        int[][] sum = new int[N+1][M+1];
        for (int i = 1; i <= N; i++) {
            int[] t = read(br);
            for (int j = 1; j <= M; j++) {
                sum[i][j] = t[j-1] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
            }
        }
        for (int i = 0; i < Q; i++) {
            int[] q = read(br);
            int x1 = q[0], y1 = q[1];
            int x2 = q[2], y2 = q[3];
            out.println(sum[x2][y2]-(sum[x1-1][y2]+sum[x2][y1-1])+sum[x1-1][y1-1]);
        }
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

99. 激光炸弹

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

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

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

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

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

输入格式

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

接下来 行，每行输入一组数据，每组数据包括三个整数 ，分别代表目标的 坐标， 坐标和价值，数据用空格隔开。

输出格式

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

数据范围

输入样例：

2 1
0 0 1
1 1 1

输出样例：

1

解法一

其实也是个模板题。.. 注意多个目标会在同一个点

import java.util.*;
import java.io.*;

class Main {

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int MAX = 5010;
        int N = in[0], R = in[1];
        int[][] w = new int[MAX][MAX];
        for (int i = 0; i < N; i++) {
            int[] t = read(br);
            w[t[0]][t[1]] += t[2];
        }
        int[][] sum = new int[MAX][MAX];
        for (int i = 1; i < MAX; i++) {
            for (int j = 1; j < MAX; j++) {
                sum[i][j] = w[i-1][j-1] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
            }
        }
        int res = 0;
        for (int i = 1; i < MAX; i++) {
            if (i+R-1 >= MAX) break;
            for (int j = 1; j < MAX; j++) {
                if (j+R-1 >= MAX) break;
                int i2 = i+R-1, j2 = j+R-1;
                res = Math.max(res, sum[i2][j2]-sum[i-1][j2]-sum[i2][j-1]+sum[i-1][j-1]);
            }
        }
        out.println(res);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

1292. 元素和小于等于阈值的正方形的最大边长

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。

请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 。

示例 1：

输入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
输出：2
解释：总和小于 4 的正方形的最大边长为 2，如图所示。

示例 2：

输入：mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
输出：0

示例 3：

输入：mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
输出：3

示例 4：

输入：mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
输出：2

提示：

解法一

这里直接将之前的 题解 搬过来了，相对来说这题就没那么模板了，结合了二分，还是挺好的

首先看到这道题就意识到了这是个二分答案的题，直接二分边长就行了，左端点 ，右端点 ，某个边长 满足的时候，大于 的都满足，某个 不满足的时候，小于 的都不满足，解空间具有单调性

所以关键问题就是check怎么写，如果直接暴力枚举所有矩形然后计算时间复杂度会很恐怖，这个时候就可以引入二维前缀和，在 的时间下求出子矩阵的和

class Solution {

    int[][] sum;

    public int maxSideLength(int[][] mat, int threshold) {
        int m = mat.length;
        int n = mat[0].length;
        int left = 1, right = Math.min(m, n);
        sum = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = mat[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
            }
        }
        int res = 0;
        while(left <= right){
            int mid = left + (right-left)/2;
            if(check(mat, mid, threshold)){
                res = mid;
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return res;
    }
    
    public boolean check(int[][] mat, int side, int threshold){
        //枚举所有的左端点
        for (int i = 1; i+side-1 <= mat.length; i++) {
            for (int j = 1; j+side-1 <= mat[0].length; j++) {
                int ri = i+side-1, rj = j+side-1;
                if(sum[ri][rj]-sum[i-1][rj]-sum[ri][j-1]+sum[i-1][j-1] <= threshold){
                    return true;
                }
            }
        }
        return false;
    }
}

798. 差分矩阵（模板题）

输入一个 行 列的整数矩阵，再输入 个操作，每个操作包含五个整数 ，其中 和 表示一个子矩阵的左上角坐标和右下角坐标。

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

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

输入格式

第一行包含整数 。

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

接下来 行，每行包含 个整数 ，表示一个操作。

输出格式

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

数据范围

输入样例：

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

解法一

二维差分模板题，一维的模板也比较简单就不多写了，二维的需要多说几句

和前缀和相反，矩阵中某个元素 的值是差分数组 到 的二维前缀和，所以当我们给某个点 的差分值加 的时候，会使以该点为左上角，到整个矩阵的右下角 的矩阵区域元素值增加
，如下图当给 的差分值增加 的时候，会使得整个蓝色框区域的矩阵元素值都增加

但是这里我们只希望子矩阵 的值增加，所以我们需要将其它区域的值减回去。所以我们给 以及 的差分值减 ，注意这两块有一个重合区域 多减了一次，我们将其加回来就行了

import java.util.*;
import java.io.*;

class Main {

    static int[][] diff;
    static int n, m, q;
    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        n = in[0]; m = in[1]; q = in[2];
        diff = new int[n+2][m+2];
        for (int i = 1; i <= n; i++) {
            int[] t = read(br);
            for (int j = 1; j <= m; j++) {
                incr(i, j, i, j, t[j-1]);
            }
        }
        for (int i = 0; i < q; i++) {
            int[] q = read(br);
            incr(q[0], q[1], q[2], q[3], q[4]);
        }
        int[][] matrix = new int[n+2][m+2];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                matrix[i][j] = diff[i][j] + matrix[i-1][j] + matrix[i][j-1] - matrix[i-1][j-1];
                out.print(matrix[i][j] + " ");
            }
            out.println();
        }
        out.flush();
    }

    public static void incr(int x1, int y1, int x2, int y2, int c) {
        diff[x1][y1] += c;
        diff[x1][y2+1] -= c;
        diff[x2+1][y1] -= c;
        diff[x2+1][y2+1] += c;
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

100. 增减序列

给定一个长度为 的数列 ，每次可以选择一个区间 ，使下标在这个区间内的数都加一或者都减一。

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

输入格式

第一行输入正整数 。

接下来 行，每行输入一个整数，第 行的整数代表 。

输出格式

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

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

数据范围

输入样例：

4
1
2

输出样例：

1
2

解法一

构建差分数组 ，根据题目要求，我们的目标就是使得 的最小操作次数，一次操作可以使得 中任意两个元素，一个加 1，一个减 1，并且求保证最小操作次数的同时， 有几种取值情况

这里我们可以将操作按照两个元素的位置进行分类：

1. 当 时， 加一（减一）， 减一（加一）
2. 当 时， 加一（减一）， 减一（加一），这种情况就只会修改 中的一个值，同时使得 值不同
3. 当 时， 加一（减一）， 减一（加一）
4. 当 时，整体加减一，没有意义

设 中正数之和为 ，负数绝对值之和为 ，那么最快使得 的操作方式就是每次从中选取一个正数一个负数，使得正数减一，负数加一，操作次数为 ，这样正负数配对后，剩下的部分就选择操作 2 或者操作 3 进行加一或者减一使其归 0，操作次数为 ，所以操作总数为：

第二问求 的取值情况，其实就是在执行完操作 1 后，剩下的部分执行 2 和 3 所能得到的不同的 值，而这 2 种操作中能影响 的值的就只有第 2 类操作，执行 次第二类操作，就会使得 加 或者减 （ 较大时 加 ，反之减 ），执行不同的次数，就能得到不同的 值，执行完操作 1 后剩余的部分一共 ，所以操作 2 的执行次数就有 种情况，对应 种 值

import java.util.*;
import java.io.*;

class Main {

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int N = read(br);
        int[] diff = new int[N+2];
        for (int i = 1; i <= N; i++) {
            int t = read(br);
            diff[i] += t; diff[i+1] -= t;
        }
        long p = 0, q = 0;
        for (int i = 2; i <= N; i++) {
            if (diff[i] > 0) {
                p += diff[i];
            } else {
                q -= diff[i];
            }
        }
        out.println(Math.max(p, q));
        out.println(Math.abs(p-q)+1);
        out.flush();
    }

    public static int read(BufferedReader br) throws Exception {
        return Integer.valueOf(br.readLine());
    }
}

1526. 形成目标数组的子数组最少增加次数

Difficulty: 困难

给你一个整数数组 target 和一个数组 initial ，initial 数组与 target  数组有同样的维度，且一开始全部为 0 。

请你返回从 initial 得到  target 的最少操作次数，每次操作需遵循以下规则：

• 在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。

答案保证在 32 位有符号整数以内。

示例 1：

输入：target = [1,2,3,2,1]
输出：3
解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 0 到 4 的元素（包含二者）加 1 。
[1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。
[1,2,2,2,1] 将下表为 2 的元素增加 1 。
[1,2,3,2,1] 得到了目标数组。

示例 2：

输入：target = [3,1,1,2]
输出：4
解释：(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。

示例 3：

输入：target = [3,1,5,4,2]
输出：7
解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。

示例 4：

输入：target = [1,1,1,1]
输出：1

提示：

解法一

31th 双周赛 t4，首先明白一点，将数组从 通过加一变为target等价于将target通过减一变为

和上面一题一样，不过这题是要连同 一起变为 0，且 ，所以 ，对应上题中就是 ，所以最小操作次数就是

​class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        res = target[0]
        for i in range(1, len(target)):
            if (d := target[i]-target[i-1]) > 0:
                res += d
        return res