官方题解（中文整理）

基于 Brian Law 的官方题解整理。

朴素做法

最直接的思路是维护整张网格上每个位置的美丽值。每次更新之后，重新枚举所有可能的 \(K \times K\) 照片，并逐格计算它们的吸引力，取最大值即可。

一共有 \((N-K+1)^2\) 张候选照片，每张照片需要 \(K^2\) 时间计算，因此每次更新复杂度为：

\(O((N-K+1)^2 K^2)\)

总复杂度为：

\(O(QN^2K^2)\)

这个做法只能通过最小的子任务。

更进一步的观察

一次更新只会改动一个格子 \( (r,c) \) 的值。于是，只有那些“包含这个格子”的照片，其吸引力才会发生变化。

一个格子 \( (r,c) \) 会出现在某张 \(K \times K\) 照片中，当且仅当这张照片左上角的行、列分别落在下面区间内：

• 行号在 \([r-K+1,\,r]\)
• 列号在 \([c-K+1,\,c]\)

再和合法范围 \([1,\,N-K+1]\) 取交，就能得到所有受影响的照片。

因此，一次更新至多影响 \(K^2\) 张照片。

正解

预先维护：

• vals[r][c]：每个格子当前的美丽值
• sum[i][j]：左上角为 \((i,j)\) 的 \(K \times K\) 照片的吸引力

当某个格子的值从旧值变成新值时，设增量为：

\(\Delta = \text{new} - \text{old}\)

那么所有包含该格子的照片，其吸引力都恰好增加 \(\Delta\)。于是我们只需要遍历这些受影响的照片，把它们的 sum 加上 \(\Delta\)。

另外，本题保证每次更新后的新值严格更大，所以每张照片的吸引力都只会单调不减。因此全局最大值也只会单调不减。这样一来，每次只要拿被更新到的这些照片去和当前最大值比较即可，不必重新扫描全部照片。

复杂度

初始化 sum 的代价是 \(O(N^2)\)。

每次更新最多改动 \(K^2\) 张照片，因此总复杂度为：

\(O(N^2 + QK^2)\)

这足以通过全部数据。