自动搬运

查看原文

来自洛谷，原作者为

	strapplE 宁教我负天下人！

搬运于2025-08-24 22:04:38，当前版本为作者最后更新于2025-05-11 10:22:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

很神秘的一个题啊。感觉真可以上位紫或者黑了。

下面我们称 X 为非障碍点，_ 为障碍点。首先做一些 trivial 的转化：多加矩形一定不会变劣，因此我们要求，所有非障碍点，都要有一个 $r\times c$ 的无障碍矩形包含它。因此 $(r,c)$ 合法当且仅当每个非障碍点都对 $r\times c$ 合法。

接下来还能观察到，显而易见的是，设 $mxc_r$ 为最大的 $c$ 使得 $(r,c)$ 合法，不存在则为 $0$。那么因为 $(r,c)$ 合法可以直接得到 $(r-1,c)$ 和 $(r,c-1)$ 合法，因此 $mxc_r$ 单调不增。因此直接暴力，你可以双指针去做，我们就可以 $O(n^3)$ 了。

但是你发现刚才的想法不太容易扩展。这只能说明我们有的性质还不太够，因此在下面，你要观察到一个最重要，也最神经的结论：

对一个固定的 $(r,c)$，如果一个点的"包围圈"都合法，它自然就合法了。

刚才是自然语言或者说是感性理解，接下来我们严谨地刻画一下：对一个非障碍点 $(x,y)$，找到包含它的极大的无障碍四连通块。如果靠在四连通块边上的点（这种点需要满足，和一个障碍点或界外相邻）都合法，则 $(x,y)$ 合法。其实这个结论比刚才说的包围圈弱一些，不过至少我会证，而且下面说的做法也只依赖于这个性质。

这个怎么理解呢？

首先你可以手摸一下，发现 $(x,y)$ 四周如果都是合法非障碍，则 $(x,y)$ 也合法。还可以做一些加强：如果三边都合法，则 $(x,y)$ 也合法（这个证明并不困难，就不说了）。我们可以在这个感觉的基础上加以证明：

现在所有边上的点都已经合法了，要证明中间的也要合法。从上往下归纳。设目前考虑到的为 $(x,y)$。

第一点：很容易发现，如果 $(x,y-k)$（其中 $1<k\leq c$）为障碍点，则取 $k$ 最小的一个，那么因为 $(x,y-k+1)$ 合法，它的矩形一定包含 $(x,y)$，所以 $(x,y)$ 合法。同理 $(x,y+k)$ 和 $(x-k,y)$ 也是。下面，我们只需要证明，蓝色部分都非障碍的基础上，$(x,y)$ 合法即可。

接下来，第二点：如果 $(x-1,y-k)$ 为障碍点，取 $k$ 最小的一个，那么 $(x-1,y-k+1)$ 合法，它的矩形如果包含 $(x,y)$ 就结束了，否则下边界为 $(x-1)$，而且此时 $x$ 这一行都非障碍，导出 $(x,y)$ 也合法，因此只需考虑 $(x-1,y-k)$ 非障碍的情况即可。

以此类推，蓝色会越来越多：

最后整个 $(r+1)\times (2c+1)$ 的部分都蓝了，那么 $(x,y)$ 显然合法了。

好了，话说这么多，就是为了证明一个结论：对于每个 $(r,c)$，只考虑边上的点的合法性和考虑所有的合法性是等价的。

那么怎么完全解决这个题呢？其实就容易多了。

对每个边上的点，我们把障碍转到它下面（对不同的障碍，共四种不同角度的转法，都要试一次），则它的矩形只能往上左右扩展。枚举它的行 $i$，设 $h_j$ 表示 $(i,j)$ 往上能走多远。则对一个下面是障碍的非障碍位置，可以形成若干个极大矩形，都取个 $\min$ 就行了。

然而这样复杂度还是三方。你会发现，很多区间是没啥用的，只需要关注"极长"的段即可。这部分我的解决方法是建小根笛卡尔树，只需要考虑它的所有子树。不过可能有更容易的做法，但是 anyway，时间复杂度是 $O(nm)$，空间可以做到除读入外 $O(n+m)$。下面给了一种实现：

#include<bits/stdc++.h>
using namespace std;
char ss[2505][2505];
int a[2505][2505],b[2505][2505];
int h[2505],d[2505],s[2505],ans[2505];
void get(int rr,int cc){
	ans[rr+1]=min(ans[rr+1],cc);
}
int ls[2505],rs[2505],st[2505],L[2505],R[2505];
void dfs(int x){
	if(ls[x]){
		dfs(ls[x]);L[x]=L[ls[x]];
		if(s[R[ls[x]]]>s[L[ls[x]]-1])get(d[x],R[ls[x]]-L[ls[x]]+1);
	}
	if(rs[x]){
		dfs(rs[x]);R[x]=R[rs[x]];
		if(s[R[rs[x]]]>s[L[rs[x]]-1])get(d[x],R[rs[x]]-L[rs[x]]+1);
	}
}
void sfd(int x){
	if(ls[x]){
		sfd(ls[x]);L[x]=L[ls[x]];
		if(s[R[ls[x]]]>s[L[ls[x]]-1])get(R[ls[x]]-L[ls[x]]+1,d[x]);
	}
	if(rs[x]){
		sfd(rs[x]);R[x]=R[rs[x]];
		if(s[R[rs[x]]]>s[L[rs[x]]-1])get(R[rs[x]]-L[rs[x]]+1,d[x]);
	}
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%s",ss[i]+1);
	for(int i=0;i<=n;++i)ans[i]=m;
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
		a[i][j]=b[j][i]=(ss[i][j]=='X');
	}
	for(int i=1;i<=m;++i)h[i]=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			h[j]=a[i][j]*(h[j]+1),s[j]=s[j-1]+(a[i][j]&&!a[i+1][j]);
			d[j]=(a[i][j]?h[j]:n+1);if(s[j]>s[j-1])get(h[j],0);
			ls[j]=rs[j]=0;d[j]=h[j];
		}
		int tt=0;
		for(int j=1;j<=m;++j){
			int lst=0;
			while(tt&&d[j]<=d[st[tt]])lst=st[tt],--tt;
			rs[st[tt]]=j;ls[j]=lst;st[++tt]=j;
			L[j]=R[j]=j;
		}
		dfs(st[1]);
	}
	for(int i=1;i<=m;++i)h[i]=0;
	for(int i=n;i>=1;--i){
		for(int j=1;j<=m;++j){
			h[j]=a[i][j]*(h[j]+1),s[j]=s[j-1]+(a[i][j]&&!a[i-1][j]);
			d[j]=(a[i][j]?h[j]:n+1);if(s[j]>s[j-1])get(h[j],0);
			ls[j]=rs[j]=0;d[j]=h[j];
		}
		int tt=0;
		for(int j=1;j<=m;++j){
			int lst=0;
			while(tt&&d[j]<=d[st[tt]])lst=st[tt],--tt;
			rs[st[tt]]=j;ls[j]=lst;st[++tt]=j;
			L[j]=R[j]=j;
		}
		dfs(st[1]);
	}
	for(int i=1;i<=n;++i)h[i]=0;
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			h[j]=a[j][i]*(h[j]+1),s[j]=s[j-1]+(a[j][i]&&!a[j][i+1]);
			d[j]=(a[j][i]?h[j]:m+1);if(s[j]>s[j-1])get(0,h[j]);
			ls[j]=rs[j]=0;d[j]=h[j];
		}
		int tt=0;
		for(int j=1;j<=n;++j){
			int lst=0;
			while(tt&&d[j]<=d[st[tt]])lst=st[tt],--tt;
			rs[st[tt]]=j;ls[j]=lst;st[++tt]=j;
			L[j]=R[j]=j;
		}
		sfd(st[1]);
	}
	for(int i=1;i<=n;++i)h[i]=0;
	for(int i=m;i>=1;--i){
		for(int j=1;j<=n;++j){
			h[j]=a[j][i]*(h[j]+1),s[j]=s[j-1]+(a[j][i]&&!a[j][i-1]);
			d[j]=(a[j][i]?h[j]:m+1);if(s[j]>s[j-1])get(0,h[j]);
			ls[j]=rs[j]=0;d[j]=h[j];
		}
		int tt=0;
		for(int j=1;j<=n;++j){
			int lst=0;
			while(tt&&d[j]<=d[st[tt]])lst=st[tt],--tt;
			rs[st[tt]]=j;ls[j]=lst;st[++tt]=j;
			L[j]=R[j]=j;
		}
		sfd(st[1]);
	}
	int mn=-1,r=0,c=0;
	for(int i=1;i<=n;++i){
		ans[i]=min(ans[i-1],ans[i]);
		if(mn<i*ans[i])mn=i*ans[i],r=i,c=ans[i];
	}
	printf("%d %d\n",r,c);
	return 0;
}