【蓝桥备赛】肖恩的投球游戏加强版—

【蓝桥备赛】肖恩的投球游戏加强版——基础二维差分

本文主要是介绍【蓝桥备赛】肖恩的投球游戏加强版——基础二维差分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

肖恩的投球游戏加强版

个人思路

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;}
}