$set$瞎搞

首先非常显然,一个矩形$(x1, y1, x2, y2)$的代价就是$\displaystyle\sum_{i = x1}^{x2}\sum_{j = y1}^{y2} h[i][j] - \min_{x1 \le i \le x2, y1 \le j \le y2} h[i][j]$,我们用$f[i][j]$表示以$(i, j)$为左上角的矩形的代价。即矩形$(i, j, i + a - 1, j + b - 1)$的代价。

我们首先考虑如何求出$f[i][j]$。

有趣的矩阵乘法

(为方便,下文中“大号宝石”代指连续的$m$个分裂出来的宝石,“小号宝石”代指未分裂的单个宝石)

首先,我们观察这题,考虑$DP​$,设状态$f_i​$表示已经取了$i​$个单元的方案数的不难推出一个朴素的$O(n^2) DP​$方程$f_i = \displaystyle\sum_{i - j \geq m} f_j +1​$(可以理解成上一个大号宝石放的位置,最后一个$1​$即为全部用小号宝石填满的方案)

我们再仔细看看这个式子,加个前缀和,不难优化到$O(n)$,然而数据范围$n \leq 10^{18}$,这让我们考虑$O(\log n)$级别的算法,我们接下来考虑矩阵乘法优化这个式子。