← 返回题目列表

Codeforces · 1661/E

E. 窄元件

中文机器翻译题面 查看原题

给定一个矩阵 $$$a$$$,由 $$$3$$$ 行和 $$$n$$$ 列组成。矩阵的每个单元格要么是空闲的,要么是被占用的。

如果至少满足以下条件之一,则可以从空闲单元格 $$$x$$$ 访问空闲单元格 $$$y$$$:

- $$$x$$$ 和 $$$y$$$ 共享一边;
- 存在一个空闲单元$$$z$$$,使得$$$z$$$可以从$$$x$$$到达并且$$$y$$$可以从$$$z$$$到达。

连接组件是矩阵的一组空闲单元,其中的所有单元都可以相互访问,但向该组添加任何其他空闲单元会违反此规则。

系统会向您询问有关矩阵的 $$$q$$$ 个查询。每个查询如下:

- $$$l$$$ $$$r$$$ - 计算矩阵的连通分量的数量,由矩阵 $$$a$$$ 的从 $$$l$$$ 到 $$$r$$$ 的列组成,包括边界值。

打印所有问题的答案。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 矩阵 $$$a$$$ 的列数。

接下来三行的第 $$$i$$$ 包含矩阵 $$$a$$$ 第 $$$i$$$ 行的描述 - 一个字符串,由 $$$n$$$ 个字符组成。每个字符要么是$$$1$$$(表示空闲单元格),要么是$$$0$$$(表示已占用的单元格)。

下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行的第 $$$j$$$ 行包含两个整数 $$$l_j$$$ 和 $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) - 第 $$$j$$$ 查询的描述。

输出

打印 $$$q$$$ 整数 - 第 $$$j$$$ 个值应等于矩阵的连通分量的数量,该矩阵由矩阵 $$$a$$$ 的从 $$$l_j$$$ 到 $$$r_j$$$ 的列组成(含)。

示例

输入 #1

12
100101011101
110110010110
010001011101
8
1 12
1 1
1 2
9 9
8 11
9 12
11 12
4 6

输出 #1

7
1
1
2
1
3
3
3