【二维st表】【二维单调队列】

本文主要是介绍【二维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<<mxlg[i-1]+1)<=i)?mxlg[i-1]+1:mxlg[i-1];
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) st[i][j][0][0]=w[i][j];
	for(int g=1;g<M;++g) for(int i=1;i+(1<<g)-1<=n;++i) for(int j=1;j<=m;++j) st[i][j][g][0]=min(st[i][j][g-1][0],st[i+(1<<g-1)][j][g-1][0]);
	for(int k=1;k<M;++k) for(int j=1;j+(1<<k)-1<=m;++j) for(int i=1;i<=n;++i) st[i][j][0][k]=min(st[i][j][0][k-1],st[i][j+(1<<k-1)][0][k-1]); 
	for(int g=1;g<M;++g) for(int k=1;k<M;++k) for(int i=1;(i+(1<<g)-1)<=n;++i) for(int j=1;j+(1<<k)-1<=m;++j) 
	st[i][j][g][k]=min(st[i][j][g][k-1],st[i][j+(1<<k-1)][g][k-1]); 
}
int ask(int a,int b,int c,int d)
{
	int k=mxlg[c-a+1],g=mxlg[d-b+1];
	return min(min(st[a][b][k][g],st[c-(1<<k)+1][b][k][g]),min(st[a][d-(1<<g)+1][k][g],st[c-(1<<k)+1][d-(1<<g)+1][k][g]));
}

但是这样空间会炸（时间可以接受），发现在查询的时候高和宽都是固定的，所以没必要保存那么多次幂的情况，只需保存用到的即可，计算时滚动即可

核心代码

void stpre()
{
	for(int i=2;i<=max(n,m);++i) mxlg[i]=((1<<mxlg[i-1]+1)<=i)?mxlg[i-1]+1:mxlg[i-1];
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) st[i][j][0][0]=w[i][j];
	for(int g=1;g<=mxlg[A-C-1];++g) for(int i=1;i+(1<<g)-1<=n;++i) for(int j=1;j<=m;++j) st[i][j][g&1][0]=min(st[i][j][g-1&1][0],st[i+(1<<g-1)][j][g-1&1][0]);
        for(int k=1;k<=mxlg[B-D-1];++k) for(int j=1;j+(1<<k)-1<=m;++j) for(int i=1;i<=n;++i) st[i][j][mxlg[A-C-1]&1][k&1]=min(st[i][j][mxlg[A-C-1]&1][k-1&1],st[i][j+(1<<k-1)][mxlg[A-C-1]&1][k-1&1]);
}
int ask(int a,int b,int c,int d)
{
	int k=mxlg[c-a+1],g=mxlg[d-b+1];
	return min(min(st[a][b][k&1][g&1],st[c-(1<<k)+1][b][k&1][g&1]),min(st[a][d-(1<<g)+1][k&1][g&1],st[c-(1<<k)+1][d-(1<<g)+1][k&1][g&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]];
	}
}

这篇关于【二维st表】【二维单调队列】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！