798. 差分矩阵

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 stub
		for(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 stub
		dif[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;
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78