自动搬运

查看原文

来自洛谷，原作者为

	dongrunxuan 知周所众，我是个*（对吧*

搬运于2025-08-24 21:17:57，当前版本为作者最后更新于2025-08-12 21:31:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B4222 [常州市赛 2023] 积木 题解

看到题解区均为二位前缀和的做法，这里提供二维 ST 表做法。

思路

首先肯定考虑二分。问题转化为求是否存在范围为 $mid\times mid$ 的矩形满足矩形内每一个元素值均大于 $mid$。

注意到这里是判断区间最小值是否大于定值，考虑使用二维 ST 表维护，注意不同于一维，二维的判断需四个值进行维护。

最后输出的值为取走的方块数，所以应输出 $sum - ans^3$。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e3+5;
int n,m,sum;
int lg[maxn];
int st[25][maxn][maxn];
int minm(int x,int y,int aa,int bb)
{
	int res=min(aa,bb);
	res=min(res,y);
	res=min(res,x);
	return res;
}
int calc(int x,int y,int len)
{
	int sz=lg[len];
	return minm(st[sz][x][y],st[sz][x+len-(1<<sz)][y],st[sz][x][y+len-(1<<sz)],st[sz][x+len-(1<<sz)][y+len-(1<<sz)]);
}
bool check(int x)
{
    for(int i=1;i<=n-x;i++)
    {
    	for(int j=1;j<=m-x;j++)
    	{
    		if(calc(i,j,x)>=x)
    		{
    			return 1;
			}
		}
	}
    return 0;
}
signed main()
{
	cin>>n>>m;
	for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>st[0][i][j];
			sum+=st[0][i][j];			
		}
	}
	int mx=lg[min(n,m)];
	for(int k=1;k<=mx;k++)
	{
		for(int i=1;i+(1<<k)-1<=n;i++)
		{
			for(int j=1;j+(1<<k)-1<=m;j++)
			{
				st[k][i][j]=minm(st[k-1][i][j],st[k-1][i+(1<<k-1)][j],st[k-1][i][j+(1<<k-1)],st[k-1][i+(1<<k-1)][j+(1<<k-1)]);
			}				
		}
	}
	int l=1,r=min(n,m);
	int ans=1;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}	
    cout<<sum-ans*ans*ans;
	return 0;
}