首先，我把英文 Editorial 翻译成人可以看的懂的英文 Editorial。（也许你还是看不懂。）
Preface: solving this problem in a time complexity of about \(300^3×log_2(300)≈2.2×10^8\) requires a descent caution on the constant factor, if not impossible. Instead, this editorial will strive to solving it in \(300^3\) time, which is actually possible.
Note the distinctive constraints of \(1≤A_i≤300\).
Recall that \(f(R)=\) (the sum of integers written on the squares in \(R\)) \(×\) (the minimum integer written on a square in \(R\)).
Let us dare to fix the minimum integer \(m\) written on a square in \(R\), which appears as the second term. There are \(300^3\) possible values.
Moreover, let us fix the bottommost column of a rectangular region. We can try \(N\) possible candidates.
Edit: Delete this paragraph.
Now consider the following value:
\(H_{i,j}=\) (when the \(i\)-th column is the bottommost one, how further can the \(j\)-th row can be extended upward, subject to the minimum value \(m\)?
Edit: \(H_{i,j}=\) You are currently at \((i,j)\). How many times you can go up one grid until you meet a number less than \(m\)?
Consider inserting columns (\(M\) times) in ascending order of \(H_{i,j}\). ...(etc.)
Edit: Consider calculating the maximal \(f\) when you are at \((i,j)\) and want the height of the resulting rectangle to be \(H_{i,j}\). You can extend left and right until you meet an invalid column. Take the maximum of all \(f\) for the answer.
We can avoid an excessive \(log\) by managing the maximal already-added consecutive rows in manner of a connected list, and sorting in ascending order of \(H_{i,j}\) based on the fact that \(H_{i,j}=H_{i-1,j}+1\) or \(H_{i,j}=0\) holds. For more details, see also the sample code.
Hence, the problem can be solved in a total of \(O(NM \max A_i)\) time.
Editorial 里面的 "solving this problem in a time complexity of about \(300^3×log_2(300)≈2.2×10^8\) requires a descent caution on the constant factor, if not impossible" 可以先不用理，因为我就是先用带 \(log\) 的 AC 的，\(1368\) ms。
这道题提示我们：
- 做题，要看数据范围（废话）。如果没有看到 \(A_{i,j}\le 300\)，这道题又会上升一个难度级别。
- （对于我）要会“正难则反”。比如说我前面的想法是对于 \((i,j)\)，bottomright corner 是 \((i,j)\) 的是多少。然后就 WA 了。其实，只需要求出每一个高度对应的 \(f\)，就同样可以解决。
带 \(loj\) 的其实就是二分左右两边。
#include <bits/stdc++.h>
using namespace std;
#define de(x) cout<<#x<<"="<<x<<endl
using ll = long long;
const int N = 3e2+2;
ll n,m;
ll a[N][N],b[N][N],h[N][N];
ll sum[N][N],s[N][N];
ll ans;
ll cal(int x1,int y1,int x2,int y2){
return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
ll cal2(int x1,int y1,int x2,int y2){
return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}
void solve(ll mn){
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
if (a[i][j]<mn){
b[i][j]=1;
}
else{
b[i][j]=0;
}
}
}
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
sum[i][j]=b[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
}
for (int j=1; j<=m; j++){
for (int i=1; i<=n; i++){
if (b[i][j]==1){
h[i][j]=0;
}
else{
h[i][j]=h[i-1][j]+1;
}
}
}
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
int l=0,r=j+1;
while (l+1<r){
int mid=l+r>>1;
if (!cal(i-h[i][j]+1,mid,i,j)){
r=mid;
}
else{
l=mid;
}
}
int L=r;
l=j-1,r=m+1;
while (l+1<r){
int mid=l+r>>1;
if (!cal(i-h[i][j]+1,j,i,mid)){
l=mid;
}
else{
r=mid;
}
}
int R=l;
ll t=cal2(i-h[i][j]+1,L,i,R)*mn;
ans=max(ans,t);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
cin>>a[i][j];
}
}
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
for (int i=1; i<=300; i++){
// min is i;
solve(i);
}
cout<<ans<<endl;
return 0;
}
// 413!413!413!
Editorial 是这样优化的：
We can avoid an excessive \(log\) by managing the maximal already-added consecutive rows in manner of a connected list, and sorting in ascending order of \(H_{i,j}\) based on the fact that \(H_{i,j}=H_{i-1,j}+1\) or \(H_{i,j}=0\) holds.
如果从大\(\rightarrow\)小，可以确定求出的 \(L,R\) 是真的 \(L,R\)。
- 如果时间范围比较紧，或者数据范围大，要尝试通过一些性质优化。
#include <bits/stdc++.h>
using namespace std;
#define de(x) cout<<#x<<"="<<x<<endl
using ll = long long;
const int N = 3e2+2;
ll n,m,ans;
ll a[N][N],s[N][N];
ll cal(int x1,int y1,int x2,int y2){
return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}
void solve(ll mn){
vector<pair<int,int> > v;
for (int i=1; i<=m; i++){
v.push_back({0,i});
}
for (int i=1; i<=n; i++){
vector<pair<int,int> > lar,sma;
for (auto u : v){
if (a[i][u.second]>=mn){
lar.push_back({u.first+1,u.second});
}
else{
sma.push_back({0,u.second});
}
}
v.clear();
for (auto u : lar){
v.push_back(u);
}
for (auto u : sma){
v.push_back(u);
}
vector<int> l(m+1),r(m+1);
for (int j=1; j<=m; j++){
l[j]=j-1,r[j]=j+1;
}
for (auto u : v){
int L=l[u.second],R=r[u.second];
if (L){
r[L]=R;
}
if (R<=m){
l[R]=L;
}
ll t=cal(i-u.first+1,L+1,i,R-1)*mn;
ans=max(ans,t);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
cin>>a[i][j];
}
}
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
for (int i=1; i<=300; i++){
// min is i;
solve(i);
}
cout<<ans<<endl;
return 0;
}
// 413!413!413!
证：\(H_{i,j}\) 单调不下降。
易得：初始满足。
\(k\rightarrow k+1\)：因为是满足的放前面，不满足的放后面。首先，\(lar\) & \(sma\) 有序。\(\min lar \ge \max sma\)。即证。