题目:https://www.luogu.org/problem/show?pid=1565

原题解似乎是 $O(n^3 * \log n)$ 的

但这题有$ O(n^3) $的做法。

虽然 https://www.luogu.org/record/show?rid=2494227 我这个$ O(n^3*\log n) $的做法跑的比我的$ O(n^3) $还快。。(应该是数据问题)

就是枚举上下边界$ x_1 $,$ x_2 $，然后枚举右端点 $ i $，

那么就是求最左的点 $ j $ 满足 $ sum_j < sum_i $ ( $ sum_i $ 表示 $ x=x_1...x_2,\,y=0...i $ 这个矩形的面积和)

如果 $ j_1 < j_2 $ 且 $ sum_{j_1} < sum_{j_2} $ ，那么 $j_2 $ 不可能成为左端点。

所以可以用单调栈维护可能的左端点，查询时二分。

$ O(n^3) $的做法:

(1) https://www.luogu.org/record/show?rid=2498503

枚举上下边界，实际上不只是可能的左端点在单调栈上，可以同理证明可能的右端点在相反的单调栈上。

从左到右枚举右端点(只枚举单调栈上的)，左端点的变化是单调的。于是可以$ O(n) $

(2) https://www.luogu.org/record/show?rid=2498807

感觉这是理论最快的做法。

原理是:当上下区间长度不变时 就是要求左右区间长度的最大值 $ mx $ , 而 $mx$ 最多变大 $ n $ 次。

长度从大到小地枚举上下边界(其实从小到大也一样)，再枚举右端点 $ i $ ，

如果以$i$为右端点的区间长度的最大值大于当前的$ mx $ ,那么 $ sum_i>min\,\, sum_j | j=[0,i-mx] $，这两者等价

所以维护这个$min$，如果发现$sum_i>min$，就++$ mx $，之后暴力重新$ O(n) $算出 $ min $。

如果上下区间长度从大到小枚举，其实长度不变或变小时都不用修改$mx$，于是最多重算$O(n)$次$min$。

从小到大枚举的话，当长度变大时需要将$mx$清0，于是最多重算$O(n^2)$次$min$。

总之总复杂度都是$O(n^3)$

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=l;i<=r;++i)
template<class T>inline void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}
template<class T>inline void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
typedef long long ll;
const int N=205;
ll s[N][N];
int ans;
ll a,_a;int w,_w;
#define get(y) (s[x2][y]-s[x1][y])

int main()
{
    freopen("1.in","r",stdin);freopen("2.out","w",stdout);
    int n,m;
    cin>>n>>m;
    rep(i,1,n)
    {
      rep(j,1,m)
      { 
        scanf("%lld",s[i]+j);
        s[i][j]+=s[i][j-1];
      }
      rep(j,1,m)
        s[i][j]+=s[i-1][j];
    }
    int mx=1;
    for(int t=n;t;--t)
    {
        int x1=0,x2=t;
      do
      {
          int i=mx;ll mn=0;//mn=min(get(0)..get(i-mx))
         do
         {
             chmin(mn,get(i-mx));
           while(get(i)>mn&&mx<=i)
           {++mx;
            mn=0;
            rep(j,1,i-mx) chmin(mn,get(j));
           }
         }while(++i<=m);
      }while(++x1,++x2<=n);
       chmax(ans,t*(mx-1));
    }
    printf("%d\n",ans);
}