CF232E Quick Tortoise

$\text{link}$

先将询问离线下来分治，设当前分治区间为 $[l,r]$ , $mid = (l + r) >> 1$，考虑处理左上角到右下角的询问，剩下的分到左右两边。

由于路径必然经过 $y=mid$ 这条直线，考虑记 $g1(i,j,k) = 1/0$ 表示 $(i,j)$ 能否走到 $(k,mid)$， $g2(i,j,k) = 1/0$ 表示 $(k,mid)$ 能否走到 $(i,j)$，

然后转移用 $bitset$ 优化一下就可以做到 $\mathrm{O(\dfrac {n^2m\log m}{\omega} + \dfrac {qn}{\omega})}$ 。

实现的时候 $(i,j)$ 的意义是反过来的（（

$\text{Code:}$

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0, f = 0; char c = getchar();
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 500 + 5;
const int maxq = 6e5 + 5;
int n, m, ans[maxq]; char c[maxn][maxn];
struct _ques {
    int xl, yl, xr, yr, id;
} qr[maxq], q0[maxq], q1[maxq];
int ck[maxn];
bitset<maxn> g1[maxn][maxn], g2[maxn][maxn];
void solve(int l, int r, int L, int R) {
    if (L > R) return;
    if (l == r) {
        for (int i = 1; i <= n; i++) ck[i] = ck[i - 1] + (c[i][r] == '#');
        for (int i = L; i <= R; i++)
        if (ck[qr[i].xr] == ck[qr[i].xl - 1]) ans[qr[i].id] = 1;
        return;
    }
    int mid = (l + r) >> 1, c0 = 0, c1 = 0;
    for (int j = l; j <= r; j++)
    for (int i = 1; i <= n; i++) g1[j][i].reset(), g2[j][i].reset();
    for (int i = 1; i <= n; i++) {
        if (c[i][mid] == '.') {
            if (i) g2[mid][i] |= g2[mid][i - 1];
            g2[mid][i].set(i);
        }
        for (int j = mid; j <= r; j++) {
            if (c[i][j] == '#') continue;
            if (i) g2[j][i] |= g2[j][i - 1];
            if (j > mid) g2[j][i] |= g2[j - 1][i];
        }
    }
    for (int i = n; i >= 1; i--) {
        if (c[i][mid] == '.') {
            if (i < n) g1[mid][i] |= g1[mid][i + 1];
            g1[mid][i].set(i);
        }
        for (int j = mid; j >= l; j--) {
            if (c[i][j] == '#') continue;
            if (i < n) g1[j][i] |= g1[j][i + 1];
            if (j < mid) g1[j][i] |= g1[j + 1][i];
        }
    }
    for (int i = L; i <= R; i++)
    if (qr[i].yr <= mid) q0[++c0] = qr[i];
    else if (qr[i].yl > mid) q1[++c1] = qr[i];
    else {
        // printf("%d %d %d\n", qr[i].id, g1[qr[i].yl][qr[i].xl].count(), g2[qr[i].yr][qr[i].xr].count());
        // for (int j = 1; j <= n; j++) printf("%d ", g1[qr[i].yl][qr[i].xl][j] ? 1 : 0); puts("");
        // for (int j = 1; j <= n; j++) printf("%d ", g2[qr[i].yr][qr[i].xr][j] ? 1 : 0); puts("");
        if ((g1[qr[i].yl][qr[i].xl] & g2[qr[i].yr][qr[i].xr]).count()) ans[qr[i].id] = 1;
    }
    for (int i = 1; i <= c0; i++) qr[L + i - 1] = q0[i];
    for (int i = 1; i <= c1; i++) qr[R - i + 1] = q1[i];
    solve(l, mid, L, L + c0 - 1);
    solve(mid + 1, r, R - c1 + 1, R);
}
int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; i++) scanf("%s", c[i] + 1);
    int q = read();
    for (int i = 1; i <= q; i++) {
        int x = read(), y = read();
        qr[i].xl = x; qr[i].yl = y;
        x = read(), y = read();
        qr[i].xr = x; qr[i].yr = y;
        qr[i].id = i;
    }
    solve(1, m, 1, q);
    for (int i = 1; i <= q; i++) puts(ans[i] ? "Yes" : "No");
    return 0;
}