题解 - C F 232 E \mathrm{CF232E} CF232E

题目意思

题目传送门

给你一张 n × m n\times m n×m 的图。 Q Q Q 次询问 ( x , y , x 1 , y 1 ) (x,y,x_1,y_1) (x,y,x1​,y1​) 问你能否从 ( x , y ) ∼ ( x 1 , y 1 ) (x,y)\sim(x_1,y_1) (x,y)∼(x1​,y1​)

n , m ≤ 500 , Q ≤ 6 e 5 n,m\leq 500,Q\leq 6e5 n,m≤500,Q≤6e5

S o l \mathrm{Sol} Sol

分治 + d p \mathrm{dp} dp + b i t s e t \mathrm{bitset} bitset 做法

我们考虑离线做。

考虑如何判定能走到，我们对于每一行 l l l 设 f i , j , k f_{i,j,k} fi,j,k​ 表示哪些 ( i , j ) ( i ∈ [ 1 , l ] ) (i,j)(i∈[1,l]) (i,j)(i∈[1,l]) 能够走到 ( l , k ) (l,k) (l,k)

同时设 g i , j , k g_{i,j,k} gi,j,k​ 哪些 ( i , j ) ( i ∈ [ l , n ] ) (i,j)(i∈[l,n]) (i,j)(i∈[l,n]) 能够走到 ( l , k ) (l,k) (l,k)。转移很简单

我们考虑分治来优化这个枚举 l l l 的过程。我们以 x x x 坐标进行分治，每次分治一边做掉一对起点终点在两端的询问。对于那些全部在一段的询问继续分治即可。

以及我们可以把 dp 用 b i t s e t \mathrm{bitset} bitset 来优化，时间复杂度 O ( log ⁡ n × n m 2 w ) O(\log n\times \frac{nm^2}{w}) O(logn×wnm2​)

C o d e \mathrm{Code} Code

int n,m,Q,Ans[M];
char ch[N][N];
struct Node
{ 
	int x,y,fx,fy,id;
};
vector<Node> que;
bitset<N> f[N][N],g[N][N];
inline void solve(int l,int r,vector<Node> v) 
{ 
	if(l>r) return;
	int mid=l+r>>1,sz=(int)v.size();
	if(!sz) return;
	Dow(i,mid,l) Dow(j,m,1) 
	{ 
		f[i][j].reset(); 
		if(ch[i][j]!='#') 
		{ 
			if(i==mid) f[i][j][j]=1;
			else f[i][j]|=f[i+1][j];
			if(j<m) f[i][j]|=f[i][j+1];
		}
	}
	For(i,mid,r) For(j,1,m) 
	{ 
		g[i][j].reset();
		if(ch[i][j]!='#') 
		{ 
			if(i==mid) g[i][j][j]=1;
			else g[i][j]|=g[i-1][j];
			if(j!=1) g[i][j]|=g[i][j-1];
		}
	}
	vector<Node> L,R;
	for(Node i:v) 
	{ 
		if(i.fx<mid) L.pb(i); 
		else if(i.x>mid) R.pb(i);
		else Ans[i.id]|=((f[i.x][i.y]&g[i.fx][i.fy]).count()>=1); 
	}
	solve(l,mid-1,L),solve(mid+1,r,R);
}
int main()
{ 
	io.read(n),io.read(m);
	For(i,1,n) scanf("%s",ch[i]+1); 
	io.read(Q);
	For(i,1,Q)
	{ 
		int x,y,fx,fy;
		io.read(x),io.read(y),io.read(fx),io.read(fy);
		que.pb((Node){ x,y,fx,fy,i});
	}
	solve(1,n,que);
	For(i,1,Q) puts((Ans[i])?"Yes":"No");
	return 0;
}