题解：P4858 [PA 2013] Karty

· · 题解

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

下面我们称 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;
}