← 返回题目列表

Codeforces · 1252/C

C. 偶数路径

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

寻路是寻找两点之间路线的任务。它经常出现在很多问题中。例如,在 GPS 导航软件中,驾驶员可以查询建议路线;在机器人运动规划中,它应该找到执行某些任务的有效运动序列;或者在简单的迷宫求解器中,它应该找到从一个点到另一个点的有效路径。这个问题与解决迷宫有关。

本问题中考虑的迷宫采用整数矩阵 $$$A$$$ 的形式,$$$N \times N$$$。每个单元格的值是从给定数组 $$$R$$$ 和 $$$C$$$ 生成的,每个数组都有 $$$N$$$ 整数。具体来说,$$$i^{th}$$$ 行和 $$$j^{th}$$$ 列(单元格 $$$(i,j)$$$)上的值等于 $$$R_i + C_j$$$。请注意,此问题中的所有索引都从 $$$1$$$ 到 $$$N$$$。

该迷宫中的路径定义为单元格序列 $$$(r_1,c_1), (r_2,c_2), \dots, (r_k,c_k)$$$,使得 $$$|r_i - r_{i+1}| + |c_i - c_{i+1}| = 1$$$ 对于所有 $$$1 \le i < k$$$。换句话说,每个相邻单元格仅相差 $$$1$$$ 行或仅 $$$1$$$ 列。该迷宫中的偶数路径被定义为路径中的所有单元格仅包含偶数的路径。

给定一个元组 $$$\langle r_a,c_a,r_b,c_b \rangle$$$ 作为查询,您的任务是确定是否存在从单元格 $$$(r_a,c_a)$$$ 到单元格 $$$(r_b,c_b)$$$ 的偶数路径。为了简化问题,保证单元格$$$(r_a,c_a)$$$和单元格$$$(r_b,c_b)$$$都包含偶数。

例如,令 $$$N = 5$$$、$$$R = \{6, 2, 7, 8, 3\}$$$ 和 $$$C = \{3, 4, 8, 5, 1\}$$$。下图描绘了从给定数组 $$$R$$$ 和 $$$C$$$ 生成 $$$5 \times 5$$$ 的矩阵 $$$A$$$。

让我们考虑几个查询:

- $$$\langle 2, 2, 1, 3 \rangle$$$:从单元格 $$$(2,2)$$$ 到单元格 $$$(1,3)$$$ 有一条偶数路径,例如 $$$(2,2), (2,3), (1,3)$$$。当然,$$$(2,2),(1,2),(1,3)$$$也是有效的偶数路径。
- $$$\langle 4, 2, 4, 3 \rangle$$$:从单元格 $$$(4,2)$$$ 到单元格 $$$(4,3)$$$ 有一条偶数路径,即 $$$(4,2), (4,3)$$$。
- $$$\langle 5, 1, 3, 4 \rangle$$$:从单元格 $$$(5,1)$$$ 到单元格 $$$(3,4)$$$ 没有偶数路径。观察到 $$$(5,1)$$$ 的唯一两个相邻单元格是单元格 $$$(5,2)$$$ 和单元格 $$$(4,1)$$$,并且它们都包含奇数(分别为 7 和 11),因此,不可能有任何源自单元格 $$$(5,1)$$$ 的偶数路径。

输入

输入以包含两个整数的行开头: $$$N$$$ $$$Q$$$ ($$$2 \le N \le 100\,000$$$; $$$1 \le Q \le 100\,000$$$) 分别表示迷宫的大小和查询的数量。下一行包含 $$$N$$$ 整数: $$$R_i$$$ ($$$0 \le R_i \le 10^6$$$) 表示数组 $$$R$$$。下一行包含 $$$N$$$ 整数: $$$C_i$$$ ($$$0 \le C_i \le 10^6$$$) 表示数组 $$$C$$$。接下来的 $$$Q$$$ 行每行包含四个整数: $$$r_a$$$ $$$c_a$$$ $$$r_b$$$ $$$c_b$$$ ($$$1 \le r_a, c_a, r_b, c_b \le N$$$) 表示 $$$\langle r_a, c_a, r_b, c_b \rangle$$$ 的查询。保证 $$$(r_a,c_a)$$$ 和 $$$(r_b,c_b)$$$ 是迷宫中的两个不同的单元格,并且它们都包含偶数。

输出

对于与输入相同顺序的每个查询,在一行中输出字符串“YES”(不带引号)或“NO”(不带引号)是否存在从单元格 $$$(r_a,c_a)$$$ 到单元格 $$$(r_b,c_b)$$$ 的偶数路径。

示例

输入 #1

5 3
6 2 7 8 3
3 4 8 5 1
2 2 1 3
4 2 4 3
5 1 3 4

输出 #1

YES
YES
NO

输入 #2

3 2
30 40 49
15 20 25
2 2 3 3
1 2 2 2

输出 #2

NO
YES

注意

示例输入/输出#1 的说明

这是问题描述中的示例。