一、题目
二、解法
考虑找中转点，也就是起点能到这个中转点并且中转点能到终点。
有一个重要的转化：要么不存在中转点，要么起点到终点的每一行都存在至少一个中转点。
那么以行为中心处理每个点到这一行的状态即可，暴力 \(\tt bitset\) 需要 \(O(\frac{n^4}{w})\)
然后我们主动使用分治，考虑中点分治，每次处理过中点的询问。可以处理出 \(b(i,j,k)\) 表示点 \((i,j)\) 是否能到达 \((mid,k)\)，可以用 \(\tt bitset\) 优化，先分治得到信息之后可以在线询问，那么时间复杂度 \(O(\frac{n^3\log n}{w}+q\log n)\)
三、总结
我觉得本题重要的是那一步转化，它缩小的答案范围，从而符合了中点分治的模型。
#include <cstdio>
#include <bitset>
using namespace std;
const int M = 505;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,q,D[4*M],num[M];char s[M][M];bitset<M> b[11][M][M];
void cdq(int x,int l,int r,int d)
{
int mid=(l+r)>>1;D[x]=d;
for(int i=1;i<=m;i++)
if(s[mid][i]=='.')
{
b[d][mid][i][i]=1;
b[d][mid][i]|=b[d][mid][i-1];
}
for(int i=mid+1;i<=r;i++)
for(int j=1;j<=m;j++)
if(s[i][j]=='.')
b[d][i][j]|=b[d][i-1][j]|b[d][i][j-1];
for(int i=m;i>=1;i--)
{
b[d][mid][i].reset();
if(s[mid][i]=='.')
{
b[d][mid][i][i]=1;
b[d][mid][i]|=b[d][mid][i+1];
}
}
for(int i=mid-1;i>=l;i--)
for(int j=m;j>=1;j--)
if(s[i][j]=='.')
b[d][i][j]|=b[d][i+1][j]|b[d][i][j+1];
if(l==r)
{
num[l]=x;
return ;
}
cdq(x<<1,l,mid,d+1);cdq(x<<1|1,mid+1,r,d+1);
}
int get(int a,int B,int c,int d)
{
int x=num[a],y=num[c];
while(D[x]>D[y]) x>>=1;
while(D[x]<D[y]) y>>=1;
while(x!=y) x>>=1,y>>=1;
return (b[D[x]][a][B]&b[D[x]][c][d]).count();
}
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
cdq(1,1,n,0);
q=read();
while(q--)
{
int a=read(),b=read(),c=read(),d=read();
if(get(a,b,c,d)) puts("Yes");
else puts("No");
}
}