[CF 480E] Parking Lot

作法：

把整個過程反過來，變成原本有很多格子是被佔的，當一格一格移除時詢問此時的答案是多少，那麼顯然答案會是遞增的。假設當前答案為$A$，那麼當移除一個格子$(x,y)$時，如果答案變大了，那就代表新的正方形一定包含了(x,y)。因此我們需要判斷「是否存在一個正方形，邊長為$A+1$，並且包含了$(x,y)$」。每次修改一個點之後就一直增加答案，直到不存在那麼大的正方形為止，那麼可以知道這個函數只會被呼叫$O(n)$次，因此可以考慮在$O(nlogn)$的時間實作他。

假設現在要處理的是包含$(x_0,y_0)$的邊長為$k$的正方形，那麼在這個正方形有覆蓋到的每一個橫排中，都包含了$y$座標為$y_0$的格子，並且這個正方形有可能覆蓋的橫排至多有$2k-1$個。因此如果我們對每個橫排，都找出$y$座標離$y_0$最近但比$y_0$小/大的格子，就知道如果那個正方形摸到了這個橫排，那麼他一定要被卡在哪兩個格子之間了。也就是對每個$i\in [x_0-k+1,x_0+k-1]$，記$L[i],R[i]$代表在這個橫排中，第$L[i]$到第$R[i]$個格子都是未被佔領的，並且其中包含了$y_0$。注意到如果$y_0$本身就已經被佔領了，那麼就可以把這個區間為設為$[y_0,y_0-1]$之類的空區間。有了這些$L,R$值之後，只要看連續$k$個橫排的$L$值的最大值，和同樣這$k$排的$R$值的最小值，看相差是否有$\geq k-1$就可以了。因此就從上往下掃，用兩個 multiset 維護$L,R$值們就好了。另外記得預處理每個橫排中有哪些被佔領的格子，把他們加入一個 set 中，才可以用 lower_bound 快速找出$L,R$的值。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000+5 ;
 
struct P{int x,y;}p[maxn];
 
int n,m,a[maxn][maxn] ;
int ans[maxn] ;
char G[maxn][maxn] ;
set<int> st[maxn] ;
multiset<int,greater<int> > stl ;
multiset<int> str ;
int L[maxn],R[maxn] ;
bool check(int x,int y,int k)
{
    int up=max(0,x-k+1) , dn=min(n-1,x+k-1) ;
    for(int i=up;i<=dn;i++)
    {
        auto it=st[i].lower_bound(y) ;
        if(*it==y){L[i]=y+1 ; R[i]=y ; continue ;}
        R[i]=*it-1 ;
        it-- ; L[i]=*it+1 ;
    }
    stl.clear() ; str.clear() ;
    for(int i=up;i<=dn;i++)
    {
        if(i>=up+k)
            stl.erase(stl.find(L[i-k])) ,
            str.erase(str.find(R[i-k])) ;
        stl.insert(L[i]) ;
        str.insert(R[i]) ;
        if(i>=up+k-1 && *str.begin()-*stl.begin() >= k-1)
            return 1 ;
    }
    return 0 ;
}
 
main()
{
    int k ; scanf("%d%d%d",&n,&m,&k) ;
    for(int i=0;i<n;i++) scanf("%s",G[i]) ;
    for(int i=1;i<=k;i++)
        scanf("%d%d",&p[i].x,&p[i].y) ,
        p[i].x-- , p[i].y-- ,
        G[p[i].x][p[i].y]='X' ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
    {
        if(G[i][j]=='X') {st[i].insert(j) ; continue ;}
        if(!i || !j) a[i][j]=1 ;
        else a[i][j]=min(min(a[i-1][j],a[i][j-1]),a[i-1][j-1])+1 ;
        ans[k]=max(ans[k],a[i][j]) ;
    }
    for(int i=0;i<n;i++) st[i].insert(-1) , st[i].insert(m) ;
 
    for(int i=k-1;i>=1;i--)
    {
        int x=p[i+1].x , y=p[i+1].y ;
        st[x].erase(y) ;
        ans[i]=ans[i+1] ;
        while(check(x,y,ans[i]+1)) ans[i]++ ;
    }
    for(int i=1;i<=k;i++) printf("%d\n",ans[i]) ;
}