P1950

题意¶

给定你一个\(n×m\)的矩阵，询问有多少个内部全是1的子矩阵。

数据范围\(1≤n,m≤1000\)。

题解¶

十分有意思的题目

对于每一个点来说，考虑以\(A(i,j)\)为右下端点的所有矩阵，可以在高最大的矩阵同底的子矩阵(1)和超出高最大的矩阵的其余矩阵(2)。

（1）¶

高自然是\(A\)点向上能到的最高为1的高（悬线长），找到这一行左边拥有一个小于这个高的悬线长的点即可求出宽，可以使用单调栈求解，这一部分

（2）¶

超出的部分所在的矩阵肯定也是一个最大矩阵类似的东西，只不过限制的高在左边，而且这个限制的高小于\(A\)点的的悬线长，你可以在这个单调栈中用双指针把所有成立的高对应的矩阵给找出，但是这样的复杂度过不去。

我们不妨逆向分析，考虑往左限制高所在的第一个点（\(P\)）进行计算。

\(A\)点在\(P\)点右侧，找\(P\)点往右所有点的贡献即可

所在矩阵有两种情况：

1.最左边的点悬线长为限制的高¶

\(P\)点往右有贡献的点的悬线高大于\(P\)点的悬线高，找到最远的第一个**小于等于** \(P\) 点悬线高的点在哪里，从这里开始都没有贡献，同样可以用单调栈找。

这时可得到一个大矩阵。

对于\(A\)点对应的所在矩阵同底的子矩阵（不为本身列的子矩阵）为与大矩阵同底的子矩阵（不为本身列的子矩阵），大矩阵本身同底的子矩阵（不为本身列的子矩阵）又均为所在矩阵或所在矩阵的子矩阵（不为本身列的子矩阵）。矩阵互不重复不重不漏。

2.中间部分的点悬线长为限制的高¶

同理但是加上了P点左边的部分。即1的方案数乘上左边最多可以延伸到何处的数量，最多可以延到第一个小于P点选项高的地方，同样用单调栈求解。

（1)+(2)¶

(1)为\(h_i\times l_i\)，（2）为\(h_i\times (r_i-1)+h_i\times (r_i-1)\times (l_i-1)=h_i\times (r_i-1)\times l_i\)，二者相加为\(h_i\times l_i \times r_i\)。

注意\(l_i\)向左第一个小于为截至，\(r_i\)向右第一个小于等于为截至。求出悬线长后，单调栈求解

启示¶