CF232E Quick Tortoise
樱雪喵
·
·
题解
设一次询问的四个参数为 (a,b,c,d)。
采用类似猫树分治的思想，对 x 坐标进行分治。
那么起点、终点在 $mid$ 同侧的可以分治到两边递归处理，我们只考虑起点在 $mid$ 上面，终点在 $mid$ 下面的询问的答案。
设 $f_{i,j,k}$ 表示从 $(i,j)$ 出发能否到达 $(mid,k)$，$g_{i,j,k}$ 表示从 $(mid,k)$ 出发能否到达 $(i,j)$。则我们可以用 $O((r-l)m)$ 的复杂度预处理这两个数组，并 $O(m+q)$ 地计算所有符合条件的询问的答案。
算上外层分治，总时间复杂度为 $O((nm^2+q)\log n)$。
过不去，但 dp 转移和判断合法的部分都可以使用 `bitset` 优化，时间复杂度 $O((\frac{nm^2}{\omega}+q)\log n)$。
```cpp
const int N=505,M=6e5+5;
int n,m,Q;
struct node{int a,b,c,d,id;} q[M],p[M];
bitset<N> f[N][N],g[N][N],a[N];
int ans[M],tot;
void solve(int l,int r,int ql,int qr)
{
if(l>r||ql>qr) return;
int mid=(l+r)>>1;
for(int j=m;j;j--)
{
f[mid][j]=0;
if(a[mid][j]) f[mid][j][j]=1,f[mid][j]|=f[mid][j+1];
}
for(int i=mid-1;i>=l;i--)
for(int j=m;j;j--) f[i][j]=a[i][j]?(f[i+1][j]|f[i][j+1]):0;
for(int j=1;j<=m;j++)
{
g[mid][j]=0;
if(a[mid][j]) g[mid][j][j]=1,g[mid][j]|=g[mid][j-1];
}
for(int i=mid+1;i<=r;i++)
for(int j=1;j<=m;j++) g[i][j]=a[i][j]?(g[i-1][j]|g[i][j-1]):0;
int nql=ql,nqr=qr;
for(int i=ql;i<=qr;i++) p[i]=q[i];
for(int i=ql;i<=qr;i++)
{
if(p[i].c<mid) q[nql++]=p[i];
else if(p[i].a>mid) q[nqr--]=p[i];
else
{
if((f[p[i].a][p[i].b]&g[p[i].c][p[i].d]).count()>0) ans[p[i].id]=1;
}
}
solve(l,mid-1,ql,nql-1),solve(mid+1,r,nqr+1,qr);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
char c;cin>>c;
a[i][j]=(c=='.');
}
Q=read();
for(int i=1;i<=Q;i++)
{
int a=read(),b=read(),c=read(),d=read();
if(a>c||b>d) continue;
q[++tot]={a,b,c,d,i};
}
solve(1,n,1,tot);
for(int i=1;i<=Q;i++) printf(ans[i]?"Yes\n":"No\n");
return 0;
}
```