「SOL」Quick Tortoise (Codeforces)

只能说没想到

题面

给出一个 \(n\times m\) 的网格图，每个格子要么是空地要么是障碍。

给出 \(q\) 个询问，每次给出 \((sx, sy),(ex,ey)\)，问从 \((sx,sy)\) 出发，只能向下或向右走，能否到达 \((ex,ey)\)。

数据规模：\(n,m\le500\)，\(q\le6\times10^5\)。

解析

只能向右或向下走就保证了转移无环，由此联想到另一道题（忘了具体哪道题了）：用线段树维护从 \((l,i)\) 到 \((r,j)\) 的路径信息。该题主要利用了两条路径比较容易合并的性质。

这道题不涉及修改，不需要线段树，可以直接猫树分治。

将询问离线，每次处理横坐标跨过区间中点的询问。对区间 \([l,r]\) 只需要预处理 \((p,i)\to(mid,k)\)（\(p\in[l,mid]\)）的连通性和 \((mid,k)\to(q,j)\)（\(q\in[mid,r]\)）的连通性即可。

询问只需要判断是否存在 \(k\) 使得路径 \((sx,sy)\to(mid,k)\to(ex,ey)\) 合法。

可以用 bitset 优化 —— 储存 \((p,i)\) 向右下走能到达 \(x=mid\) 的哪些点，以及 \((q,j)\) 向左上走能到达 \(x=mid\) 的哪些点。查询可以一次 bitset 求交集。

复杂度 \(\mathcal{O}(\frac{n^3\log n+nq}{w})\)。

源代码

/* Lucky_Glass */

#include <bitset>

#include <cstdio>

#include <cassert>

#include <cstring>

#include <algorithm>

#define CON(typ) const typ &

const int N = 505, M = 6e5 + 10;

int rin(int &r) {

  int c = getchar(); r = 0;

  while (c < '0' || '9' < c) c = getchar();

  while ('0' <= c && c <= '9') r = r * 10 + (c ^ '0'), c = getchar();

  return r;

}

int n, m, qry_cnt;

char maz[N][N];

int qry[M][4], qry_id[M], tmp_id[M];

bool ans[M];

std::bitset<N> dp[N][N], dp_rev[N][N];

void solve(CON(int) xl, CON(int) xr, CON(int) ql, CON(int) qr) {

  if (ql > qr) return;

  assert(xl <= xr);

  int mi = (xl + xr) >> 1;

  for (int j = m; j; --j)

    if (maz[mi][j] == '.') dp[mi][j] = dp[mi][j + 1], dp[mi][j].set(j, 1);

    else dp[mi][j] = 0;

  for (int i = mi - 1; i >= xl; --i)

    for (int j = m; j; --j)

      if (maz[i][j] == '.') dp[i][j] = dp[i + 1][j] | dp[i][j + 1];

      else dp[i][j] = 0;

  for (int j = 1; j <= m; ++j)

    if (maz[mi][j] == '.') {

      dp_rev[mi][j] = dp_rev[mi][j - 1], dp_rev[mi][j].set(j, 1);

    } else {

      dp_rev[mi][j] = 0;

    }

  for (int i = mi + 1; i <= xr; ++i)

    for (int j = 1; j <= m; ++j)

      if (maz[i][j] == '.') dp_rev[i][j] = dp_rev[i - 1][j] | dp_rev[i][j - 1];

      else dp_rev[i][j] = 0;

  int qll = ql - 1, qrr = qr + 1;

  for (int i = ql; i <= qr; ++i)

    if (qry[qry_id[i]][0] <= mi && mi <= qry[qry_id[i]][2]) {

      int *now = qry[qry_id[i]];

      ans[qry_id[i]] = (dp[now[0]][now[1]] & dp_rev[now[2]][now[3]]) != 0;

    } else if (qry[qry_id[i]][0] > mi) {

      tmp_id[--qrr] = qry_id[i];

    } else {

      tmp_id[++qll] = qry_id[i];

    }

  for (int i = ql; i <= qll; ++i) qry_id[i] = tmp_id[i];

  for (int i = qrr; i <= qr; ++i) qry_id[i] = tmp_id[i];

  solve(xl, mi - 1, ql, qll);

  solve(mi + 1, xr, qrr, qr);

}

int main() {

  rin(n), rin(m);

  for (int i = 1; i <= n; ++i) scanf("%s", maz[i] + 1);

  rin(qry_cnt);

  for (int i = 1; i <= qry_cnt; ++i) {

    rin(qry[i][0]), rin(qry[i][1]), rin(qry[i][2]), rin(qry[i][3]);

    qry_id[i] = i;

  }

  solve(1, n, 1, qry_cnt);

  for (int i = 1; i <= qry_cnt; ++i)

    printf("%s\n", ans[i] ? "Yes" : "No");

  return 0;

}

THE END

Thanks for reading!

历过沧海的变迁
再难为江河的涡旋
我寻找着沉默的桑田坎坷万千
眺望过巫山之巅
再不是浮云的翩跹
我寻找着属于我的那片云烟
在下个时刻出现

——《巫山云》By Snapmod / 诗岸

Link 巫山云 - 网易云

巴特西

「SOL」Quick Tortoise (Codeforces)

题面

解析

源代码

THE END

Thanks for reading!

最新文章

热门文章