给出 \(n\times m\) 的矩阵 \(a\)。求权值最大子矩形的权值。
一个矩形的权值定义为它里面全部数的和乘上最小值。
\(n,m\leq 300,0\leq a_{i,j}\leq 300\)。
枚举最小的数 \(a_{i,j}\)。则在满足 \(a_{i,j}\) 是最小值时，包含 \((i,j)\) 的矩形一定是极大的。
这些矩形不好枚举，也难以计算究竟有多少个。
考虑添加一些限制。
枚举上下边界。那么我们枚举列，以这一列的最小值为待定矩形的最小值，然后向左右拓展为一个极大的矩形。
发现这样拓展出的矩形与上面做法的矩形形成双射。
拓展可以采用二维 ST 表+二分实现。时间复杂度 \(O(n^3\log{n})\)。
哦还可以单调栈。时间是 \(O(n^3)\)。
单调栈：
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define rg register
#define ld long double
#define ull unsigned long long
#define gc getchar
#define pc putchar
#define pob pop_back
#define ump unordered_map
#define vi vector<int>
#define vl vector<ll>
#define fo(i,l,r) for(rg int i=(l);i<=(r);++i)
using namespace std;
inline int re() {
rg int x=0,p=0;rg char c=getchar();
while(c<'0'||c>'9') (!p)?(p=c=='-'):(p=p),c=getchar();
while('0'<=c&&c<='9') (x*=10)+=c-48,c=getchar();
if(p) x=-x;
return x;
}
inline ll rel() {
rg ll x=0;rg int p=0;rg char c=getchar();
while(c<'0'||c>'9') (!p)?(p=c=='-'):(p=p),c=getchar();
while('0'<=c&&c<='9') (x*=10)+=c-48,c=getchar();
if(p) x=-x;
return x;
}
inline void wt(rg int x) { if(x<0) pc('-'),x=-x;if(x>9) wt(x/10);pc(x%10+48); }
inline void wtl(rg ll x) { if(x<0) pc('-'),x=-x;if(x>9) wtl(x/10);pc(x%10+48); }
const int N=305;
const int Lg=9;
int n,m,a[N][N],s[N][N],ql[N],qr[N],mn[N],stl;
struct pr { int v,i; }sta[N];
ll ans;
inline int Sum(rg int l1,rg int r1,rg int l2,rg int r2) {
return s[l2][r2]-s[l1-1][r2]-s[l2][r1-1]+s[l1-1][r1-1];
}
int main() {
// freopen(".in","r",stdin),freopen(".out","w",stdout);
n=re(),m=re();
fo(i,1,n) {
fo(j,1,m) {
a[i][j]=re();
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
fo(x,1,n) {
fo(i,1,m) mn[i]=1000;
fo(y,x,n) {
fo(i,1,m) mn[i]=min(mn[i],a[y][i]);
stl=0;
fo(i,1,m) {
while(stl&&sta[stl].v>=mn[i]) stl--;
if(stl) ql[i]=sta[stl].i+1;
else ql[i]=1;
sta[++stl]={mn[i],i};
}
stl=0;
for(rg int i=m;i>=1;--i) {
while(stl&&sta[stl].v>=mn[i]) stl--;
if(stl) qr[i]=sta[stl].i-1;
else qr[i]=m;
sta[++stl]={mn[i],i};
}
fo(i,1,m) {
ans=max(ans,1ll*mn[i]*Sum(x,ql[i],y,qr[i]));
}
}
}
wtl(ans);
}
ST 表：
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define rg register
#define ld long double
#define ull unsigned long long
#define gc getchar
#define pc putchar
#define pob pop_back
#define ump unordered_map
#define vi vector<int>
#define vl vector<ll>
#define fo(i,l,r) for(rg int i=(l);i<=(r);++i)
using namespace std;
inline int re() {
rg int x=0,p=0;rg char c=getchar();
while(c<'0'||c>'9') (!p)?(p=c=='-'):(p=p),c=getchar();
while('0'<=c&&c<='9') (x*=10)+=c-48,c=getchar();
if(p) x=-x;
return x;
}
inline ll rel() {
rg ll x=0;rg int p=0;rg char c=getchar();
while(c<'0'||c>'9') (!p)?(p=c=='-'):(p=p),c=getchar();
while('0'<=c&&c<='9') (x*=10)+=c-48,c=getchar();
if(p) x=-x;
return x;
}
inline void wt(rg int x) { if(x<0) pc('-'),x=-x;if(x>9) wt(x/10);pc(x%10+48); }
inline void wtl(rg ll x) { if(x<0) pc('-'),x=-x;if(x>9) wtl(x/10);pc(x%10+48); }
const int N=305;
const int Lg=9;
int n,m,st[N][N][Lg][Lg],g[N],c[N],s[N][N];
ll ans;
int query(int l1,int r1,int l2,int r2) {
int sl=g[l2-l1+1],sr=g[r2-r1+1];
// printf("%d %d %d %d = %d\n",l1,r1,l2,r2,min({st[l1][r1][sl][sr],st[l1][r2-(1<<sr)+1][sl][sr],st[l2-(1<<sl)+1][r1][sl][sr],st[l2-(1<<sl)+1][r2-(1<<sr)+1][sl][sr]}));
return min({st[l1][r1][sl][sr],st[l1][r2-(1<<sr)+1][sl][sr],st[l2-(1<<sl)+1][r1][sl][sr],st[l2-(1<<sl)+1][r2-(1<<sr)+1][sl][sr]});
}
int Sum(int l1,int r1,int l2,int r2) {
return s[l2][r2]-s[l1-1][r2]-s[l2][r1-1]+s[l1-1][r1-1];
}
int main() {
// freopen(".in","r",stdin),freopen(".out","w",stdout);
fo(i,2,300) g[i]=g[i/2]+1;
n=re(),m=re();
fo(i,1,n) {
fo(j,1,m) {
st[i][j][0][0]=re();
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+st[i][j][0][0];
}
}
fo(x,0,g[n]) {
fo(y,0,g[m]) {
if(!x&&!y) continue;
for(int i=1;i+(1<<x)-1<=n;i++) {
for(int j=1;j+(1<<y)-1<=m;j++) {
if(!x) st[i][j][x][y]=min(st[i][j][x][y-1],st[i][j+(1<<y-1)][x][y-1]);
else if(!y) st[i][j][x][y]=min(st[i][j][x-1][y],st[i+(1<<x-1)][j][x-1][y]);
else st[i][j][x][y]=min({st[i][j][x-1][y-1],st[i][j+(1<<y-1)][x-1][y-1],st[i+(1<<x-1)][j][x-1][y-1],st[i+(1<<x-1)][j+(1<<y-1)][x-1][y-1]});
}
}
}
}
fo(x,1,n) {
fo(y,x,n) {
fo(i,1,m) {
int p=query(x,i,y,i),ql,qr;
int L=1,R=i;
while(L<=R) {
int mid=L+R>>1;
if(query(x,mid,y,i)==p) R=(ql=mid)-1;
else L=mid+1;
}
L=i,R=m;
while(L<=R) {
int mid=L+R>>1;
if(query(x,i,y,mid)==p) L=(qr=mid)+1;
else R=mid-1;
}
ans=max(ans,1ll*p*Sum(x,ql,y,qr));
}
}
}
wtl(ans);
}