题解：CF1920F2 Smooth Sailing (Hard Version)

Solve F1 first.
模拟赛中学到的一般性的做法

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

一些简单的约定：

设 $N=nm$ 。
称一个点被 ban 了当且仅当它在被选择的路径上。
赋予这个网格图上的点 $(x,y)$ 新标号 $(x-1)\bmod m+y$ （目的单纯是转为我们日常习惯的一维数组与表达）。本文形如“点 $(x,y)$ ”表示网格图中对应的点的坐标，形如点 $x$ 表示重标号后为 $x$ 的点。

本题解将给出一个

O(N\log^2 N)

的解决方案。

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

G

来刻画这个问题：

对于网格上没有被 ban 的点 $x$ 与点 $y$ ，如果两点八联通，则连边 $x\leftrightarrow y$ 。
建立超级源点 $S$ ，对于边界上的点 $x$ ，连边 $x\leftrightarrow S$ 。
建立超级汇点 $T$ ，对于 $s_{x,y}=\text{\#}$ ，即岛屿，连边 $(x,y)\leftrightarrow T$ 。
则存在岛屿能到达边界当且仅当 $S$ 和 $T$ 连通。

这样我们用一个点数和边数都是

O(N)

，且每个点的度数为

O(1)

的图将问题转换为连通性。

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

我们从树的角度切入，处理一次查询点

(x,y)

的答案，可以二分点

(x,y)

在 Kruskal 重构树上的祖先

anc

，然后可以选入路径的点的集合就是 $anc$ 的子树，这个观察非常厉害！我们的做法变为：

二分 $(x,y)$ 在 Kruskal 重构树上的祖先 $anc$ ，每次判断：如果将 $anc$ 的子树里的点全部从 $G$ 中移除， $S$ 和 $T$ 是否依旧连通。

对于子树问题，我们可以把 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

已经被加入；结束时，撤销到开始时的状态。我们用图文来解释这个过程（横线中用红色表示当前最新的操作，黑色/红色表示对应点当前被加入，竖线表示当前处理的区间）：

初始，solve(l,r,L,R)：

第一步：加入 $a_{mid}\sim a_R$ ：

第二步：从左到右加点，找到 $S$ 和 $T$ 连通的第一个位置 $pos$ ：

这时候我们发现，对于

i\in[pos,r]

，

g_i\ge mid

，对于

i\in [l,pos-1]

，

g_i<mid

。

第三步，撤销第二步中的操作，为向左递归铺垫。这样我们回到了第一步中的图。
第四步，向左递归，即 solve(l,pos-1,L,mid-1)。

第五步，向左递归结束，在左区间造成的所有操作被撤销，再次回到第一次的图。
第六步，撤销第一步的操作，为向右递归做铺垫，回到初始的图。
第七步，加入 $[l,pos-1]$ 中的点，为向右递归做铺垫。

第八步，向右递归，即 solve(pos,r,mid,R)。

第九步，向右递归结束，操作被撤销，回到第七步中的图。
第十步，撤销第七步中的操作，回到初始状态，我们的目标达成！

容易发现，虽然每次 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

就行，还有很多细节可以自己研究。

CPP

#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;
}

题解：CF1920F2 Smooth Sailing (Hard Version)

文章操作

相关推荐

评论

题解：CF1920F2 Smooth Sailing (Hard Version)