题解：CF1920F2 Smooth Sailing (Hard Version)

· · 题解

我们去除题目中的特殊性质：岛屿构成一个四联通块，即岛屿可以在除了边界上的任何位置，问题变为是否存在岛屿能到达边界，这题还能够完成吗？

一些简单的约定：

本题解将给出一个 O(N\log^2 N) 的解决方案。

在去掉特殊性质后，如果要判断岛屿能否到达边界，就无法使用现有题解的特殊方法。不过我们可以用一张无向图 G 来刻画这个问题：

这样我们用一个点数和边数都是 O(N)，且每个点的度数为 O(1) 的图将问题转换为连通性。

然后是和现有题解一样的思路，我们要最大化路径权值的最小值，可以使用 Kruskal 重构树。

我们从树的角度切入，处理一次查询点 (x,y) 的答案，可以二分点 (x,y) 在 Kruskal 重构树上的祖先 anc，然后可以选入路径的点的集合就是 anc 的子树，这个观察非常厉害！我们的做法变为：

对于子树问题，我们可以把 Kruskal 重构树用 dfn 序转为区间！设非岛屿点的数量为 M，现在问题变为有序列 a_{1\sim M}，多次查询区间 [l,r]，若从 G 中删除 a_l\sim a_r 的点，S 与 T 是否连通。

我们尝试对于每个位置 l，求出最小的 r 使得如果删除 a_l\sim a_r 中的点， S 和 T 不连通，设其为 f_l。

显然 f_l 可以双指针，不过我们的操作为加边、删边、维护连通性，非常 LCT 困难。

但是我们可以利用 f_l 的单调性进行整体二分。并使用可撤销并查集维护连通性。

这样的做法要求我们的加入和撤销要有很清晰的顺序，否则复杂度和正确性难以保证，这里呕象将很详细的教大家怎么用整体二分解决这个问题。

我们把删除 [l,r] 看作保留 a_1\sim a_{l-1} 与 a_{r+1}\sim a_M 中的点，即保留一段前缀和一段后缀，这样操作就只有加点（同时加入这个点带来的边），求出 g_l 表示如果保留前 l 个点，最大的 r 使得保留 a_{r+1}\sim a_M 中的点，S 和 T 仍然连通。

接下来，用 solve(l,r,L,R) 表示当前要处理 g_l\sim g_r，它们的取值范围是 [L,R]，我们二分答案 mid=\lfloor\frac{L+R+1}{2}\rfloor。

我们的想法是保证当 solve(l,r,L,R) 开始时，a_1\sim a_{l-1} 和 a_{R+1}\sim a_M 已经被加入；结束时，撤销到开始时的状态。我们用图文来解释这个过程（横线中用红色表示当前最新的操作，黑色/红色表示对应点当前被加入，竖线表示当前处理的区间）：

这时候我们发现，对于 i\in[pos,r]，g_i\ge mid，对于 i\in [l,pos-1]，g_i<mid。

容易发现，虽然每次 solve 考虑的区间是 [l,R]，但是每次 solve 的复杂度为 O((r-l+1+R-L+1)\log N)，这两部分在每层的总和都是 O(n) 的，所以复杂度足以保障。

这样我们就可以在 O(N\log^2 N) 的时间求出所有的 g_l，从而得到所有的 f_l。最终我们可以在 kruskal 重构树上倍增代替二分，check 是 O(1) 的，所以查询是 O(q\log N)。总复杂度为 O(N\log^2 N)。

有一点点边界情况，比如如果 a_1\sim a_l 保留时 S 和 T 已经连通，就令 g_l=M+1。这个只需要在初始时令 R=M+1 就行，还有很多细节可以自己研究。

#include<bits/stdc++.h>
#define mid ((l+r)>>1)
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
#define pb push_back
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
#define Pi pair<int,int>
#define ui unsigned ll
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
using namespace std;
const int N=1e5+5,M=3e5+5,inf=(1LL<<30)-1,dx[8]={1,0,-1,0,1,1,-1,-1},dy[8]={0,1,0,-1,1,-1,1,-1};
int n,m,q,val[M],fa[M][20],G[M],tp,S,T,h[M],to[M],nxt[M],cnt,f[M],sz[M],dfn[M],Id[M],siz[M],Time,rt;
int id(int x,int y){return (x-1)*m+y;}
string s[N];
vector<int>a[N];
vector<bool>v[N];
bool che(int X,int Y){return X&&Y&&X<=n&&Y<=m;}
void bfs(){
    queue<Pi>q;
    repn(i)repm(j)a[i][j]=inf;
    repn(i)repm(j)if(s[i][j]=='v')a[i][j]=0,q.push({i,j});
    while(!q.empty()){
        int x=q.front().first,y=q.front().second;q.pop();
        val[id(x,y)]=a[x][y];
        rep(i,0,3){
            int X=x+dx[i],Y=y+dy[i];
            if(!che(X,Y))continue;
            if(a[X][Y]==inf)a[X][Y]=a[x][y]+1,q.push({X,Y});
        }
    }
}
int Find(int x){return f[x]==x?x:f[x]=Find(f[x]);}
int find(int x){return f[x]==x?x:find(f[x]);}
void add_(int a,int b){to[++cnt]=b,nxt[cnt]=h[a],h[a]=cnt;}
struct edge{int x,y,w;}g[M<<1];
bool cmp(edge a,edge b){return a.w>b.w;}
void dfs(int x,int Fa){
    Id[dfn[x]=++Time]=x,siz[x]=1,fa[x][0]=Fa;
    rep(i,1,18)fa[x][i]=fa[fa[x][i-1]][i-1];
    e(x)dfs(y,x),siz[x]+=siz[y];
}
struct op{
    int x,y;
}st[M];
void Undo(int t){while(tp>t)sz[st[tp].y]-=sz[st[tp].x],f[st[tp].x]=st[tp].x,tp--;}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(sz[x]>sz[y])swap(x,y);
    if(x!=y)f[x]=y,sz[y]+=sz[x],st[++tp]={x,y};
}
bool F[M];
void Insert(int ID){
    if(!ID)return;
    int x=(ID-1)/m+1,y=(ID-1)%m+1;
    v[x][y]=1;
    rep(i,0,7){
        int X=x+dx[i],Y=y+dy[i];
        if(che(X,Y)&&v[X][Y])merge(id(x,y),id(X,Y));
    }
    if(x==1||y==1||x==n||y==m)merge(id(x,y),S);
    if(s[x][y]=='#')merge(id(x,y),T);
}
void Refuse(int ID){
    if(!ID)return;
    int x=(ID-1)/m+1,y=(ID-1)%m+1;
    v[x][y]=0;
}
void solve(int l,int r,int Ll,int Rr){
    if(l>r||Ll>Rr)return;
    if(Ll==Rr){
        rep(i,l,r)G[i]=Ll;
        return;
    }
    int Mid=Ll+Rr+1>>1,TiM=tp,Tim,pos=l-1;
    rep(i,Mid,Rr)Insert(Id[i]);
    Tim=tp;
    if(find(S)!=find(T)){
        rep(i,l,r+1){
            pos=i;
            if(i==r+1)break;
            Insert(Id[i]);
            if(find(S)==find(T))break;      
        }
    }
    rep(i,l,min(pos,r))Refuse(Id[i]);
    Undo(Tim),solve(l,pos-1,Ll,Mid-1);
    rep(i,Mid,Rr)Refuse(Id[i]);
    Undo(TiM),pos=max(pos,l);
    rep(i,l,pos-1)Insert(Id[i]);
    solve(pos,r,Mid,Rr);
    rep(i,l,pos-1)Refuse(Id[i]);
    Undo(TiM);
}
void SolveG(){
    rep(i,1,n*m+2)f[i]=i,sz[i]=1;
    S=n*m+1,T=S+1;
    rep(i,1,Time)G[i]=0;
    repn(x)repm(y)if(s[x][y]=='#')Insert(id(x,y));
    tp=0;
    solve(1,Time-1,1,Time+1);
    rep(i,1,Time-1)G[i]=max(G[i],i+1),F[i+1]=G[i]<=i+siz[Id[i+1]];
    F[1]=1;
}
void Main(){
    n=read(),m=read(),q=read();
    rep(i,0,n+1)a[i].resize(m+2),v[i].resize(m+2);
    repn(i)cin>>s[i],s[i]=' '+s[i];
    bfs();
    int ct=0;
    repn(x)repm(y)if(s[x][y]!='#'){
        rep(i,0,1){
            int X=x+dx[i],Y=y+dy[i];
            if(!che(X,Y)||s[X][Y]=='#')continue;
            g[++ct]={id(x,y),id(X,Y),min(val[id(x,y)],val[id(X,Y)])};
        }
    }
    rep(i,1,n*m)f[i]=i;
    sort(g+1,g+ct+1,cmp);
    rep(i,1,ct){
        int x=g[i].x,y=g[i].y;
        x=Find(x),y=Find(y);
        if(x==y)continue;
        if(val[x]>=val[y])f[x]=y,add_(y,x),rt=y;
        else f[y]=x,add_(x,y),rt=x;
    }
    dfs(rt,0),SolveG(),F[0]=1;
    while(q--){
        int x=read(),y=read(),Nw=id(x,y);
        if(F[dfn[Nw]]){
            cout <<val[Nw]<<'\n';
            continue;
        }
        per(i,18,0)if(!F[dfn[fa[Nw][i]]])Nw=fa[Nw][i];
        cout <<val[fa[Nw][0]]<<'\n';
    }
    repn(x)repm(y)v[x][y]=0,h[id(x,y)]=0,Id[id(x,y)]=0;
    rep(x,1,n*m)rep(y,0,18)fa[x][y]=0;
    cnt=Time=rt=0;
}
signed main(){
    int T=1;
    while(T--)Main();
    return 0;
}