题目理解

我们有一个 $n \times n$ 的矩阵 $a$，每次操作可以选择一个正方形子矩阵，将其主对角线上的所有元素增加 $1$。
目标：使得矩阵中所有元素非负，求最少操作次数。

关键观察

1. 操作只影响同一条对角线上的元素

设一个元素 $(i, j)$ 的对角线编号为：

注意：这个 $d$ 在主对角线上是常数，因为：

因此，一次操作（选择某个正方形的主对角线）只会影响所有 $d(i, j)$ 相同的元素。

2. 不同对角线的操作是独立的

因为一次操作只能增加一条固定对角线上的元素（准确说是该对角线上在选定正方形区域内的连续一段），但不同对角线的元素永远不会在同一次操作中被同时增加。

因此，我们可以分别处理每条对角线，最后将所需操作次数相加。

问题化简

对于一条固定的对角线（例如 $d = c$），其上的元素是矩阵中所有满足 $i - j = c$ 的位置。

我们要用最少的操作，使这条对角线上的所有元素非负。
一次操作可以增加该对角线上一段连续的元素（对应正方形区域）。
但注意：我们可以从 $(i, j)$ 到 $(i+k, j+k)$ 增加，这就是该对角线上的一段。

为了使得总操作数最少，我们应该尽可能在一次操作中覆盖更多需要增加的位置。
然而，因为每次操作只能增加 $1$，并且不同位置需要的增加次数可能不同，所以其实这个问题等价于：

对于这条对角线上的每个元素，它需要被增加若干次，且每次增加可以覆盖一段连续的区间。
但仔细分析：由于我们可以任意选择起始位置和长度，实际上我们可以独立地对每个元素增加任意次数吗？

实际上，更简单的结论是：

• 对于某条对角线，设其上的最小值为 $m$。如果 $m \ge 0$，则该对角线已经全部非负，不需要操作。
• 如果 $m < 0$，那么我们需要让所有元素都至少增加 $-m$（因为最小值要变成非负）。
  但一次操作只能增加 $1$，并且只能增加连续的一段。
  然而，如果我们选择整个对角线所在的最大正方形（即从对角线一端到另一端），我们可以在一次操作中给整个对角线上的所有元素 $+1$。
  因此，我们只需要对整个对角线整体加 $1$ 的操作重复 $-m$ 次 即可。

那是否会有浪费？
比如对角线上的元素是 $[-2, -1, 3]$，最小值是 $-2$，那么整体加两次：得到 $[0, 1, 5]$，没问题。
如果尝试局部操作可能更优？不能，因为要解决最小的 $-2$，必须加至少两次到那个位置，而加它的同时一定会影响到它的同行列其他对角线上元素吗？
不影响：注意我们只能加该对角线上的元素，并且一次操作可以只加它一个（选择 $1 \times 1$ 的正方形），所以我们可以独立地给每个位置增加次数。
但为了最优，实际上我们就是按每个元素需要的增加次数取最大值？不，因为一次操作可能覆盖多个位置。

关键结论：
对于一条对角线，需要的操作次数等于该对角线上最小元素的绝对值的负数部分（如果最小值为负）。
即：

为什么？
因为一次操作可以同时给整条对角线（或其中的连续段）加 $1$，但为了把最小的负值变成非负，至少需要加 $-\min$ 次。
并且我们可以这样构造：每次操作选择从该对角线的最小值位置到该对角线末尾（或开头）的连续段，保证覆盖最小值位置及其它需要增加的负数位置，这样 $-\min$ 次操作后全部非负。
不会更多，因为最小值必须加那么多次。

实现方法

我们遍历所有对角线（$d = i - j$ 从 $-(n-1)$ 到 $n-1$），对每条对角线：

• 遍历它的所有元素，找到最小值 $m$。
• 如果 $m < 0$，答案加上 $-m$。

时间复杂度：每个元素被访问一次，$O(n^2)$。

示例验证

例 3：

1   2   3
-2  1  -1
0   0  -1

对角线 $d = 0$（主对角）：$1, 1, -1$，最小 $-1$，加 $1$ 次。
$d = -1$：$2, -1$，最小 $-1$，加 $1$ 次。
$d = -2$：$3$，最小 $3$，加 $0$。
$d = 1$：$-2, 0$，最小 $-2$，加 $2$。
$d = 2$：$0$，加 $0$。
总计 $1+1+0+2+0 = 4$，匹配输出。

最终结论

答案 = $\sum_{\text{每条对角线}} \max(0, -\min(\text{对角线元素}))$