我们知道，如果我们确定了每个大矩形包含的权值最小的小矩形，那么我们只需要枚举一遍每一个大矩形并比较它们的回形部分的最大值。
那么我们考虑用单调队列来预处理出每一个小矩形的权值，然后用二维线段树来维护这个权值，那么我们可以在\(n^2log^2n\)的时间复杂度内完成这道题。
但仔细观察我们感觉\(n^2log^2n\)的时间复杂度对于\(1000\)的数据范围存在一定的困难。我们考虑是否存在一种\(n^2\)复杂度的做法。
有这样一道题叫做理想的正方形。这一题要求的是平面上矩形内最大值和最小值之差。显然，我们可以维护2n个单调队列来计算这个最大值。
那么，对于这题的强化板，我们该怎么做呢？
如果确定了右下角，那么整个矩形的权值是已经固定了的。那么，我们要求的就是那个矩形里面权值最小的子矩形。这一方面是和理想的正方形相同的。
我们不妨设\(c_{i,j}\)表示以(i,j)为右下角的绿化带能包括的花坛的最小值。问题就转变为怎么求出\(c_{i,j}\)。
仔细考虑这个问题，我们发现，每个花坛的最小值是可以预处理的。这样，我们就把这一题转化为了理想的正方形。
同样用二维单调队列维护即可。
需要注意边界条件较为复杂，且不要混淆单调队列里的数的意义。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=1005;
int n,m,A,B,C,D;
int val[N][N],sm[N][N],a[N][N],b[N][N];
deque<int> q[N],qq;
void init(){
scanf("%d%d%d%d%d%d",&n,&m,&B,&A,&D,&C);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%d",&val[i][j]);
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
sm[i][j]=val[i][j]+sm[i][j-1]+sm[i-1][j]-sm[i-1][j-1];
}
}
for(int i=B;i<=n;++i){
for(int j=A;j<=m;++j){
b[i][j]=sm[i][j]-sm[i-B][j]-sm[i][j-A]+sm[i-B][j-A];
// printf("%d ",b[i][j]);
}
// puts("");
}
for(int i=D;i<=n;++i){
for(int j=C;j<=m;++j){
a[i][j]=sm[i][j]-sm[i-D][j]-sm[i][j-C]+sm[i-D][j-C];
// printf("%d ",a[i][j]);
}
// puts("");
}
int ans=0;
for(int i=D+1;i<n;++i){
for(int j=C+1;j<m;++j){
// printf("%d %d\n",i,j);
while(!q[j].empty()&&a[q[j].back()][j]>a[i][j]){q[j].pop_back();}
q[j].push_back(i);
while(!q[j].empty()&&i-q[j].front()>B-D-2){q[j].pop_front();}
}
while(!qq.empty()){qq.pop_back();}
for(int j=C+1;j<m;++j){
while(!qq.empty()&&a[q[qq.back()].front()][qq.back()]>a[q[j].front()][j]){qq.pop_back();}
qq.push_back(j);
while(!qq.empty()&&j-qq.front()>A-C-2){qq.pop_front();}
if(!qq.empty()&&i>=B-1&&j>=A-1){ans=max(ans,b[i+1][j+1]-a[q[qq.front()].front()][qq.front()]);}
}
}
printf("%d\n",ans);
}
int main(){
init();
return 0;
}