Decrease

题目描述 给定一个 $n \times n$ 的矩阵，你可以进行若干次操作。
每次操作，你可以将一个 $k \times k$ 的连续子矩阵里的所有数全部加上 1 或者全部减去 1。
起始时，矩阵中有 $m$ 个位置上的数不为 0，其它位置上的数均为 0。
请你求出至少需要多少次操作，可以使矩阵中所有数都变为 0。
输入格式

第一行三个整数 $n, m, k$，分别表示矩阵大小、非 0 项数和每次修改的连续子矩阵大小。
接下来 $m$ 行，每行三个整数 $x, y, z$，表示初始时矩阵的第 $x$ 行第 $y$ 列上的数为 $z$。
输出格式
一行一个整数，表示最少操作次数。
特别地，如果无法使矩阵中所有数都变为 0，输出 -1。
输入输出样例

样例输入 #1
Plaintext

样例输出 #1
Plaintext
-1
样例输入 #2
Plaintext
2 1 2
1 1 1
样例输出 #2
Plaintext
-1

1. 核心思路：贪心策略

这道题要求我们用最小的操作次数将矩阵变为全 $0$。

唯一确定性：当我们从矩阵的左上角 $(1, 1)$ 开始按行（或按列）遍历时，对于当前位置 $(i, j)$，如果我们已经保证了 $(i, j)$ 左边和上边的所有元素都变成了 $0$，那么当前位置 $(i, j)$ 的非零值只能通过以 $(i, j)$ 为左上角的 $k \times k$ 矩阵操作来消除。
为什么？ 因为任何左上角坐标小于 $(i, j)$ 的 $k \times k$ 矩阵都会影响到已经归零的区域，而任何左上角坐标大于 $(i, j)$ 的矩阵都覆盖不到 $(i, j)$。
推论：从 $(1, 1)$ 遍历到 $(n, n)$，遇到非零值就“定点清除”，这就是最优（次数最少）且唯一的解法。

2. 技术手段：二维差分

如果直接对 $k \times k$ 区域进行暴力修改，单次操作复杂度为 $O(k^2)$，总复杂度会达到 $O(n^2 k^2)$，显然会超时。
我们需要维护增量的二维差分。设差分数组为 $d[i][j]$，它记录的是我们进行的“操作”。
当我们决定在 $(i, j)$ 开启一个值为 $v$ 的修改（即该区域所有数加 $v$）时，我们只需要修改 $d$ 数组的四个关键点：

$d[i][j] \gets d[i][j] + v$
$d[i+k][j] \gets d[i+k][j] - v$
$d[i][j+k] \gets d[i][j+k] - v$
$d[i+k][j+k] \gets d[i+k][j+k] + v$
通过计算 $d$ 数组的二维前缀和，我们可以 $O(1)$ 地得到当前格子 $(i, j)$ 累计受到的增量。

3. 算法步骤

输入处理：用数组 a[n][n] 存储初始的 $m$ 个非零点。
动态遍历：
- 使用双重循环遍历 $i, j \in [1, n]$。
- 利用二维前缀和公式计算出 $(i, j)$ 当前的实际值：
  $now = a[i][j] + (\text{之前所有操作在 } i, j \text{ 处产生的增量})$
- 如果 $now \neq 0$：
  - 检查合法性：如果以 $(i, j)$ 为左上角放不下 $k \times k$ 的矩阵（即 $i+k-1 > n$ 或 $j+k-1 > n$），说明这个值永远无法消掉，直接输出 -1。
  - 执行操作：令操作值 $v = -now$。累加操作次数 $ans += |v|$。
  - 更新差分：在 $d$ 数组上标记这 4 个点。
结果输出：遍历结束，输出总次数 $ans$。

4. 复杂度分析

时间复杂度：$O(n^2)$。我们需要遍历整个矩阵一次，每次计算前缀和与更新差分都是 $O(1)$ 的。
空间复杂度：$O(n^2)$。需要存储原矩阵和差分矩阵。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 使用 long long 防止操作次数和中间计算溢出
typedef long long ll;

/**
 * 核心逻辑：
 * 1. 从左上角 (1, 1) 开始贪心遍历。
 * 2. 利用二维差分维护区域修改，利用前缀和实时获取当前格子的值。
 * 3. 发现当前值不为 0 时，必须以当前点为左上角开启一个 k*k 的操作。
 */

int main() {
    // 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;

    // arr 存储原始矩阵，diff 记录操作的二维差分
    // 多开空间防止 i+k, j+k 越界
    vector<vector<ll>> arr(n + k + 2, vector<ll>(n + k + 2, 0));
    vector<vector<ll>> diff(n + k + 2, vector<ll>(n + k + 2, 0));
    // s 用于存储 diff 的二维前缀和，即当前点受到的累计增量
    vector<vector<ll>> s(n + k + 2, vector<ll>(n + k + 2, 0));

    // 读取 m 个非零点
    for (int i = 0; i < m; i++) {
        int x, y;
        ll z;
        cin >> x >> y >> z;
        arr[x][y] = z;
    }

    ll total_ops = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // 计算当前格子受到的所有历史操作影响
            // 二维前缀和公式：S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + D[i][j]
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + diff[i][j];
            
            // 当前格子的真实值 = 初始值 + 累计修改增量
            ll current_val = arr[i][j] + s[i][j];

            if (current_val != 0) {
                // 如果当前格子的值不为 0，必须消除它
                // 检查是否可以作为 k*k 矩阵的左上角进行操作
                if (i + k - 1 <= n && j + k - 1 <= n) {
                    ll op = -current_val; // 使当前值归零需要的操作量
                    total_ops += abs(op);
                    
                    // 更新二维差分数组（4点修改法）
                    diff[i][j] += op;
                    diff[i + k][j] -= op;
                    diff[i][j + k] -= op;
                    diff[i + k][j + k] += op;
                    
                    // 重要：同步更新当前格子的前缀和状态，使其立即归零
                    s[i][j] += op; 
                } else {
                    // 如果无法放置 k*k 矩阵且当前值不为 0，说明无法清零
                    cout << -1 << endl;
                    return 0;
                }
            }
        }
    }

    cout << total_ops << endl;
    return 0;
}