CF1661E Narrow Components

给定一个由 $3$ 行 $n$ 列组成的矩阵 $a$。矩阵中的每个单元格要么是空闲的，要么是被占用的。 如果至少满足以下条件之一，则空闲单元格 $y$ 可以从空闲单元格 $x$ 到达： - $x$ 和 $y$ 共享一条边； - 存在一个空闲单元格 $z$，使得 $z$ 可以从 $x$ 到达，且 $y$ 可以从 $z$ 到达。 一个连通块是指矩阵中一组空闲单元格，这些单元格两两可达，并且加入任意其他空闲单元格都会破坏这个性质。 你需要回答 $q$ 个关于该矩阵的询问。每个询问如下： - $l$ $r$ —— 统计由矩阵 $a$ 的第 $l$ 列到第 $r$ 列（包含）组成的子矩阵中的连通块数量。 请输出所有询问的答案。

第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$），表示矩阵 $a$ 的列数。 接下来的三行，每行包含一个长度为 $n$ 的字符串，描述矩阵 $a$ 的第 $i$ 行。每个字符为 $1$（表示空闲单元格）或 $0$（表示被占用单元格）。 接下来一行包含一个整数 $q$（$1 \le q \le 3 \cdot 10^5$），表示询问的数量。 接下来的 $q$ 行，每行包含两个整数 $l_j$ 和 $r_j$（$1 \le l_j \le r_j \le n$），表示第 $j$ 个询问。

输出 $q$ 个整数，第 $j$ 个数表示对于第 $j$ 个询问，子矩阵中连通块的数量。

由 ChatGPT 4.1 翻译