2409. 编辑子矩阵
1000ms
256MB
简单
前缀和与差分
题目描述
有一个 $n \times n$ 大小的方阵，矩阵中的初始值为 $0$。现在有 $k$ 次操作，每次操作会将矩阵中以 $(x_1, y_1)$ 为左上角、$(x_2, y_2)$ 为右下角的子矩阵中的每个数加 $1$。
请输出经过 $k$ 次操作后，方阵中每个元素的值。
输入格式
- 第一行包含两个整数 $n$ 和 $k$ ($n, k \le 1000$)。
- 接下来 $k$ 行，每行包含 $4$ 个整数 $x_1, y_1, x_2, y_2$。
- 数据保证所有坐标均在方阵范围内，且左上角坐标 $\le$ 右下角坐标。
输出格式
- 输出 $n$ 行，每行 $n$ 个整数，代表最终方阵中每个元素的值。
样例 1
输入 (Input)
5 3 2 2 3 3 3 3 5 5 1 2 1 4
输出 (Output)
0 1 1 1 0 0 1 1 0 0 0 1 2 1 1 0 0 1 1 1 0 0 1 1 1
- $1 \le n, k \le 1000$
- 坐标范围：$1 \le x_1, x_2, y_1, y_2 \le n$
### **算法提示**
- **二维差分**：对于矩形区域修改，直接遍历会达到 $O(k \cdot n^2)$ 复杂度，可能超时。使用二维差分可以将单次修改降至 $O(1)$。
- **还原矩阵**：修改完成后，通过计算二维前缀和还原出原矩阵，总复杂度为 $O(k + n^2)$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功