[ABC311G] One More Grid Task

题意

给一个矩阵，定义一个矩阵的价值为其最小值乘上总和，问子矩阵中最大价值。

题解

感觉有些简单，不配在G这个位置。

观察贡献的形式，我们需要维护最小值与还有和。

首先第一个想法是以最小值为分治点来分治，划分区域。
但是对比一维的情况来说就复杂太多了，不是很现实。

仔细想一想分治的目的是什么，是为了确定最小值，观察数据发现值域很小。
考虑枚举最小值 \(x\)，只能选大于等于 \(x\) 的数，所以将大于等于 \(x\) 的值设为 \(1\)，反之设为 \(0\) 。
所以我们就是要找出一个 \(\sum a_{i,j}\) 最大的子矩阵，并且不能有设为 \(0\) 的数。

这其实就是一个 最大子矩阵和 的变形，考虑使用悬线法来解决。
我们对于每一个数找到 \(h_{i,j}\) 表示最长向上能选多长。
想象一根线向下移动就可以快速求出 \(h_{i,j}\)，我们对于点 \((i,j)\) ，令高为 \(h_{i,j}\)，贪心得在同一行求出左边和右边第一个小于 \(h_{i,j}\) 的位置就可以求出最长的长了，显然可以通过单调栈实现。
最后通过二维前缀和得到矩形和就行了，code