题目链接
个人思路
q 次对一个 n * m 的矩阵操作,我们肯定不能对这个矩阵每次都进行修改,不然复杂度就是 O (q n m) 也就是 1e11, 明显会超时的。
那么,我们就需要拿一个数组记录下这 q 次操作都干了什么?
while(q--)
{
int x1, y1, x2, y2;
ll c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
brr[x1][y1] += c;
brr[x1][y2 + 1] -= c;
brr[x2 + 1][y1] -= c;
brr[x2 + 1][y2 + 1] += c;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j<= m; ++j)
brr[i][j] += brr[i - 1][j] + brr[i][j - 1] - brr[i - 1][j - 1];
这里brr数组初始是一个空的数组。在这里我们将这 q 次进行标记,并通过求前缀和获得对于每一个单元格的操作结果,到底是 +10 了还是 -4 了,都清晰的显示在 brr 数组上。
之后,我们就可以将 arr数组 + brr数组 得到修改后的 arr 数组。
for(int i = 1; i <= n; ++i)
for(int j = 1; j<= m; ++j)
arr[i][j] += brr[i][j];
参考代码
C/C++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
int n, m, q;
ll arr[N][N], brr[N][N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> q;
for(int i = 1; i <= n; ++i)
for(int j = 1; j<= m; ++j)
cin >> arr[i][j];
while(q--)
{
int x1, y1, x2, y2;
ll c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
brr[x1][y1] += c;
brr[x1][y2 + 1] -= c;
brr[x2 + 1][y1] -= c;
brr[x2 + 1][y2 + 1] += c;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j<= m; ++j)
brr[i][j] += brr[i - 1][j] + brr[i][j - 1] - brr[i - 1][j - 1];
for(int i = 1; i <= n; ++i)
for(int j = 1; j<= m; ++j)
arr[i][j] += brr[i][j];
for(int i = 1; i <= n; ++i)
for(int j = 1; j<= m; ++j)
cout << arr[i][j] << " \n"[j == m];
}
Java
import java.io.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner();
int n = sc.nextInt();
int m = sc.nextInt();
int q = sc.nextInt();
long[][] arr = new long[n + 5][m + 5];
long[][] brr = new long[n + 5][m + 5];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
arr[i][j] = sc.nextLong();
while (q-- > 0) {
int x1 = sc.nextInt();
int y1 = sc.nextInt();
int x2 = sc.nextInt();
int y2 = sc.nextInt();
long c = sc.nextLong();
brr[x1][y1] += c;
brr[x1][y2 + 1] -= c;
brr[x2 + 1][y1] -= c;
brr[x2 + 1][y2 + 1] += c;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
brr[i][j] += brr[i - 1][j] + brr[i][j - 1] - brr[i - 1][j - 1];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
arr[i][j] += brr[i][j];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
System.out.print(arr[i][j]);
System.out.print(j == m ? "\n" : " ");
}
}
}
class Scanner {
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public long nextLong() {
try {
st.nextToken();
} catch (IOException e) {
throw new RuntimeException(e);
}
return (long) st.nval;
}
public int nextInt() {
try {
st.nextToken();
} catch (IOException e) {
throw new RuntimeException(e);
}
return (int) st.nval;
}
}