题解：P13889 [蓝桥杯 2023 省 Python A] 子矩阵

题目需要让我们求出在$n*m$的矩阵里每个大小为$a*b$的子矩阵最大值最小值乘积的和。

对于数据范围，仅仅3秒，暴力枚举求和显然不够（时间复杂度为$O(nmab)$，对于全数据就是$10^{12}$）。这个时候我们需要想办法优化。

我们发现，这个$n*m$的矩阵是不会有任何数被修改的。也就是说，我们可以采用离线的做法预处理每一个子矩阵的两个最值。对于这种RMQ问题，我们通常会使用单调队列和st表解决。考虑到时间复杂度在使用单调队列的情况下能够达到最优，我就单独讲述单调队列做法。（二位数列做单调队列能达到约$O(nm)$，而st表在时间和空间上会较大，需要额外优化）

先说一下一维数组的单调队列，可先去单调队列模板看一看，稍微了解一番。

我们会发现，在长为$k$的区间里，枚举去比较会让除了开头$k-1$和末尾$k-1$的数以外的所有数都参与比较多次，无用的枚举占据的多部分时间。

我们既然需要在连续的$k$个数中求出最值，我们不妨使用一个双端队列实时更新最值。显然，当我们求最大值的时候，若一个数字从序列添加到队列末尾，并且这个数要比队前的数要大，那么前面的数就失去了在这一段区间里竞争最大值的资格，可以直接弹出队列。求最小值也是同理。

考虑到区间长度为$k$，于是在当前数字下标$i$和队头$q.front()$满足下列关系时，该队头就不属于此区间，需要弹出。

这一个队列的核心用处就是求出最值，那么它肯定也保证处于队头的必定时查询区域中的最值。每个数只会入队和出队各一次，完全不会有多余比较，时间复杂度降到了$O(n)$

子矩阵大小$a*b$，其实就变相地告诉了我们单调队列需要维护的区间长度。用$O(nm)$的时间枚举矩阵，用两个双端队列维护子区间的最大、最小值，再用两个二维数组同步保存当前$i$行$j$列的最大、小值即可。

对于矩阵中每一个数字，其范围为$1\leq A_{i,j} \leq 10^9$。需要考虑最小值和最大值都为$10^9$，还要乘积的情况，为了防止在$mod998244353$前就超出int范围，我们需要开long long变量保存。另一个，在统计答案总和时，我们需要计算一次取模一次。具体为何，请看下列数据（十分极端的数据）

每个子矩阵可贡献$10^{18}$，有$10^6$个这样的子矩阵，加在一起的总和巨大。所以在计算过程中需要频繁地取模，防止溢出。