本文共 3102 字，大约阅读时间需要 10 分钟。

方法一：dp

这个做法还是很神奇的。当$k>1$时，考虑一个$k\ast k$的子矩阵，我们将最大值假定为右下角的值，那么我们统计答案时，只需要统计矩阵$[(k,k),(n,m)]$，而$k\ast k$的子矩阵一定可以由若干个重叠的$2\ast 2$的矩阵构成，那么我们就只需要每次将左边和上面的最值传递到当前位置，这样最后的答案和最后的矩阵没有关系，只和统计开始的行列有关系

#include 
   
    #include 
    
   

方法二：单调队列

实际上对每一行和每一列来说，我们只需想办法求出每$k$长度的一段的最大值。这个时候可能会想到线段树，ST表等等，但是内存显然不允许这么做，实际上这不就是滑动窗口的最值问题吗？那么使用单调队列，具体做法为：

首先操作每一行，将每个行中$1-k$的最值存到第$k$个位置，然后操作每一列，将每列中$1-k$的最值存到第$k$个位置，那么最后只需要查询每个$k\ast k$矩阵的右下角求和

#include 
   
    #include