题目描述

二维差分

样例

import java.util.Scanner;

public class Main {

    /*
    给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上 c：

    b[x1, y1] += c, b[x2 + 1, y1] -= c, b[x1, y2 + 1] -= c, b[x2 + 1, y2 + 1] += c

    private static final int N = 1010;
    private static final int[][] a = new int[N + 5][N + 5];//不要也许
    private static final int[][] s = new int[N + 5][N + 5];
    private static final int[][] b = new int[N + 5][N + 5];

    private static void difference(int x1, int y1, int x2, int y2, int c) {
        b[x1][y1] += c;
        b[x2 + 1][y1] -= c;
        b[x1][y2 + 1] -= c;
        b[x2 + 1][y2 + 1] += c;
    }

    private static void sumPrefix(int n, int m) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + b[i][j];
            }
        }
    }
    */

    private static final int N = 1010;
    private static final int[][] a = new int[N + 5][N + 5];//不要也行
    private static final int[][] s = new int[N + 5][N + 5];
    private static final int[][] b = new int[N + 5][N + 5];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = in.nextInt();//
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                difference(i, j, i, j, a[i][j]);//求二维差分数组
            }
        }

        while (q-- > 0) {
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();
            int c = in.nextInt();
            difference(x1, y1, x2, y2, c);
        }

        sumPrefix(n, m);

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                System.out.print(s[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static void difference(int x1, int y1, int x2, int y2, int c) {
        b[x1][y1] += c;
        b[x2 + 1][y1] -= c;
        b[x1][y2 + 1] -= c;
        b[x2 + 1][y2 + 1] += c;
    }

    private static void sumPrefix(int n, int m) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + b[i][j];//用二维前缀和的方法求出最后的数组
            }
        }
    }
}