【二维st表】【二维单调队列】
【二维st表】【二维单调队列】
修筑绿化带
分析：
首先可以枚举大矩形的右下角，用前缀和算出大矩形的面积和。
接下来考虑快速计算出面积最小的小矩形是多少，可以发现对于一个固定的大矩形，小矩形的右下角的取值范围也构成一个矩形，定义w[i][j]为以(i,j)为右下角，C*D的矩阵的面积和，那么每次我们只需快速求出这个矩形的w的最小值
假设大矩形的右下角为(i,j）,则不难推出查询范围：
右下角：(i-1,j-1)
左下角：(i-1,j-B+D+1)
右上角：(i-A+C+1,j-1)
左上角：(i-A+C+1,j-B+D+1)
高：A-C-1
宽：B-D-1
求二维矩形的最值，我们可以类比一维，使用st表预处理。
可以设st[i][j][k][g]表示以(i,j)为左上角，高为\(2^k\),长为\(2^g\)的矩形中的最小值，则k，g为阶段,先预处理st[i][j][0][0],再计算st[i][j][0][g],st[i][j][k][0],在计算st[i][j][k][g]即可。
询问用4个矩形拼凑即可
核心代码
void stpre()
{
for(int i=2;i<=max(n,m);++i) mxlg[i]=((1<但是这样空间会炸（时间可以接受），发现在查询的时候高和宽都是固定的，所以没必要保存那么多次幂的情况，只需保存用到的即可，计算时滚动即可
核心代码
void stpre()
{
for(int i=2;i<=max(n,m);++i) mxlg[i]=((1<但是既然都发现查询的矩形形状是固定的了，干嘛还用st表呢？考虑我们在一维状态下，如果查询区间固定的话，可以用单调队列线性计算，二维同理。
先用单调队列对每个点求出从这个点往上h个单位（h为查询矩形的高）中的最小值up[i][j]，在用类似的方法横着做一遍单调队列，就能算出以(i,j)为右下角的矩形的最小值wd[i][j]
代码：
for(int j=1;j<=m;++j)
{
l=1,r=0;
for(int i=1;i<=a;++i)
{
while(l<=r&&w[q[r]][j]>=w[i][j])r--;
q[++r]=i;
}
up[a][j]=w[q[l]][j];
for(int i=a+1;i<=n;++i)
{
while(l<=r&&w[q[r]][j]>=w[i][j]) r--;
q[++r]=i;
if(q[l]==i-a) l++;
up[i][j]=w[q[l]][j];
}
}
for(int i=a;i<=n;++i)
{
l=1,r=0;
for(int j=1;j<=b;++j)
{
while(l<=r&&up[i][q[r]]>=up[i][j]) r--;
q[++r]=j;
}
wd[i][b]=up[i][q[l]];
for(int j=b+1;j<=m;++j)
{
while(l<=r&&up[i][q[r]]>=up[i][j]) r--;
q[++r]=j;
if(q[l]==j-b) l++;
wd[i][j]=up[i][q[l]];
}
}