Problem: 798. 差分矩陣

思路

這是一個差分矩陣的問題。差分矩陣是一種用于處理區間修改問題的數據結構，它可以在O(1)的時間復雜度內完成區間的修改操作，然后在O(n)的時間復雜度內完成所有元素的更新操作。

在這個問題中，我們需要處理的操作是在一個二維矩陣的某個子矩陣內所有元素加上一個常數。這可以通過修改子矩陣的四個角的值來實現。具體來說，左上角和右下角的值需要加上這個常數，而右上角和左下角的值需要減去這個常數。

然后，我們需要輸出修改后的矩陣。這可以通過計算每個元素的前綴和來實現。前綴和是一個常用的技巧，它可以在O(1)的時間復雜度內查詢任意區間的和。

解題方法

首先，我們需要讀入矩陣的大小和初始值，然后處理所有的修改操作。每個修改操作都會修改四個角的值。

然后，我們需要計算每個元素的前綴和。這可以通過遍歷矩陣并累加每個元素的左上角的值來實現。

最后，我們需要輸出修改后的矩陣。這可以通過遍歷矩陣并輸出每個元素的值來實現。

復雜度

時間復雜度:

$O(n^2)$，其中n是矩陣的大小。我們需要遍歷矩陣兩次，一次是處理修改操作，一次是計算前綴和。

空間復雜度:

$O(n^2)$，其中n是矩陣的大小。我們需要存儲矩陣的值和差分矩陣的值。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);static int n, m, q;static int MAXN = (int) (1e3 + 10);static int[][] arr = new int[MAXN][MAXN];static int[][] dif = new int[MAXN][MAXN];public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();q = nextInt();for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {arr[i][j] = nextInt();}}for (int i = 0, x1, y1, x2, y2, c; i < q; i++) {x1 = nextInt();y1 = nextInt();x2 = nextInt();y2 = nextInt();c = nextInt();set(x1, y1, x2, y2, c);}build();for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {out.print(arr[i][j] + dif[i][j] + " ");}out.println();}clear();out.flush();}public static void clear() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {dif[i][j] = 0;}}}private static void build() {// TODO Auto-generated method stubfor(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {dif[i][j] += dif[i - 1][j] + dif[i][j - 1] - dif[i - 1][j - 1];}}}private static void set(int x1, int y1, int x2, int y2, int c) {// TODO Auto-generated method stubdif[x2 + 1][y2 + 1] += c;dif[x1][y1] += c;dif[x2 + 1][y1] -= c;dif[x1][y2 + 1] -= c;}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}