类型：单调队列
传送门：>Here<
题意：给出一个$M*N$的矩阵，每一个代表这一格土地的肥沃程度。现在要求修建一个$C*D$的矩形花坛，矩形绿化带的面积为$A*B$，要求花坛被包裹在绿化带中，且不能碰到绿化带边缘。问绿化带的最大肥沃程度
解题思路
暴力做法：枚举绿化带，然后选出能使其肥沃程度最大的花坛位置。
很容易发现要使绿化带的肥沃程度最大，也就是让所选的花坛的肥沃程度尽量小。由此，问题转化为了求固定矩形内部规定大小的最小子矩形
为了表达方便，以下称绿化带为矩形$AB$，花坛为矩形$CD$。
为了计算方便，我们可以先预处理出以$(i,j)$为右下角的矩形$AB$和矩形$CD$的肥沃程度。利用前缀和处理即可
显然固定矩形$AB$以后，矩形$CD$的可取范围也被固定了。这个范围是可以计算的。设矩形$AB$的右下角为$(i+1,j+1)$，则矩形$CD$的右下角可取范围是$(i+1-(A-1)+C ightarrow i, j+1-(B-1)+D ightarrow j)$。也就是$$(i-A+C+2 ightarrow i, j-B+D+2 ightarrow j)$$由于我们已经计算出了以$(i,j)$为右下角的矩形$CD$的肥沃程度，因此我们可以把每一个格子看做是一个矩形$CD$。于是要求以同一个$i$作为右下角横坐标的矩形时，他们就是一个横行里的格子。用一个单调队列就很容易求出
求出范围内每一个横行的最小值以后，对所有这些最小值再竖着用单调队列求一个最小值。即可以得出整个范围内的最小值。问题就解决了
这题的代码实现也很难（本蒟蒻打了2.5h+），由于边界条件如此的坑而且样例又如此的水，不得不自己造了好几组数据一个一个调……关键在于把控清楚每一个数组表示的具体内容，包括要不要$+1或-1$
Code
/*By DennyQi 2018.8.19*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #define r read() #define Max(a,b) (((a)>(b)) ? (a) : (b)) #define Min(a,b) (((a)<(b)) ? (a) : (b)) using namespace std; typedef long long ll; const int MAXN = 1010; const int INF = 1061109567; inline int read(){ int x = 0; int w = 1; register int c = getchar(); while(c ^ '-' && (c < '0' || c > '9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c >= '0' && c <= '9') x = (x<<3) + (x<<1) + c - '0', c = getchar(); return x * w; } int M,N,A,B,C,D,h,t; int a[MAXN][MAXN],sum[MAXN][MAXN],ab[MAXN][MAXN],cd[MAXN][MAXN]; int q[MAXN],mcd[MAXN][MAXN],mx[MAXN][MAXN]; int main(){ N = r, M = r; A = r, B = r, C = r, D = r; for(int i = 1; i <= N; ++i){ h = 1, t = 0; for(int j = 1; j <= M; ++j){ a[i][j] = r; sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j]; ab[i][j] = sum[i][j] - sum[i][j-B] - sum[i-A][j] + sum[i-A][j-B]; cd[i][j] = sum[i][j] - sum[i][j-D] - sum[i-C][j] + sum[i-C][j-D]; if(i > C && j > D && i < N && j < M){ while(h <= t && cd[i][q[t]] >= cd[i][j]) --t; q[++t] = j; if(j - B + D + 2 > 0){ while(h <= t && q[h] < j - B + D + 1) ++h; } if(i > C && j > D) mcd[i][j] = cd[i][q[h]]; } } } for(int k = B; k <= M; ++k){ h = 1, t = 0; q[0] = 0; for(int i = C+1; i <= N; ++i){ while(h <= t && q[h] < i - A + C + 1) ++h; if(i >= A) mx[i][k] = mcd[q[h]][k-1]; while(h <= t && mcd[q[t]][k-1] >= mcd[i][k-1]) --t; q[++t] = i; } } int ans = 0; for(int i = A; i <= N; ++i){ for(int j = B; j <= M; ++j){ ans = Max(ans, ab[i][j] - mx[i][j]); } } printf("%d", ans); return 0; }