[AdditionalFile5353.zip](file://AdditionalFile5353.zip?type=additional_file)

#5353. 「OOI 2025 Day 1」爱丽丝、鲍勃和两个数组

标签: 传统 | 时间限制: 2500 ms | 内存限制: 1024 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2025 Day1 T1 「Алиса, Боб и два массива / Alice, Bob, and two arrays」。

有一个长度为 $N$ 的数组 $a$ 和一个长度为 $M$ 的数组 $b$。这两个数组中的所有数字都是整数，且范围在 $1$ 到 $k$ 之间。此外，还有一个初始为空的数组 $c$。

爱丽丝和鲍勃在这两个数组上玩一个游戏：玩家轮流进行操作，在自己的回合中，玩家必须在数组 $c$ 的末尾添加一个数字，使得 $c$ 始终是数组 $a$ 和数组 $b$ 的子序列。无法进行操作的玩家输掉游戏。爱丽丝首先进行操作。

他们将进行 $q$ 次游戏。在第 $i$ 次游戏中，他们会选择两个数字 $x_i$ 和 $y_i$ $(0 \leq x_i < N, 0 \leq y_i < M)$，然后从数组 $a$ 中删除前 $x_i$ 个数字，从数组 $b$ 中删除前 $y_i$ 个数字，并在处理后的数组上进行游戏。每次游戏结束后，在开始下一次游戏之前，他们会将数组 $a$ 和 $b$ 恢复到初始状态，即在某次游戏中删除的数字不会影响后续游戏。此外，数组 $c$ 在每次游戏之间会被清空。

由于他们有自己的习惯，他们总是选择 $x_i$ 和 $y_i$，使得删除后数组 $a$ 和 $b$ 的剩余部分以相同的值开始。

爱丽丝非常希望获胜，因此她请求你对于每次游戏，回答她是否能在双方玩家都采用最优策略的情况下赢得游戏。

请注意，数组可能非常长，因此它们以特殊方式输入。每个数组以一组连续相同数字的段来描述。数组 $a$ 由 $n$ 个这样的段组成，数组 $b$ 由 $m$ 个这样的段组成。每个段由其长度和该段上的数字值定义。

输入格式

第一行包含六个整数 $N, n, M, m, k, q$ $(1 \leq N, M \leq 10^{9}, 1 \leq n, m, k \leq 1600, 1 \leq q \leq 10^{6})$，分别表示第一个数组的长度、第一个数组的段数、第二个数组的长度、第二个数组的段数、数字范围的上限以及游戏次数。

接下来的 $n$ 行，每行包含两个整数 $l^a_i$ 和 $v^a_i$ $(1 \leq l^a_i \leq N, 1 \leq v^a_i \leq k)$，分别表示段的长度和该段中数字的值。这些数字定义数组 $a$：前 $l^a_1$ 个数字均为 $v^a_1$，接下来的 $l^a_2$ 个数字均为 $v^a_2$，……，最后 $l^a_n$ 个数字均为 $v^a_n$。

接下来的 $m$ 行，每行包含两个整数 $l^b_i$ 和 $v^b_i$ $(1 \leq l^b_i \leq M, 1 \leq v^b_i \leq k)$，分别表示段的长度和该段中数字的值。这些数字定义数组 $b$，格式与数组 $a$ 类似。

保证 $\sum l^a_i = N$，$\sum l^b_i = M$，并且 $v^a_i \neq v^a_{i+1}, v^b_i \neq v^b_{i+1}$。

接下来的 $q$ 行，每行包含一对整数 $x_i$ 和 $y_i$ $(0 \leq x_i < N, 0 \leq y_i < M)$，描述每次游戏的删除操作。

对于每次游戏 $i$，保证删除数组 $a$ 的前 $x_i$ 个元素和数组 $b$ 的前 $y_i$ 个元素后，剩余部分的第一个数字值相同。

输出格式

对于 $q$ 次游戏中的每一次，如果在双方玩家都采用最优策略的情况下爱丽丝能获胜，在单独的一行中输出 Yes；如果鲍勃能获胜，输出 No。

样例 1

输入

5 1 5 1 1 9
5 1
5 1
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

输出

Yes
No
Yes
No
No
Yes
Yes
Yes
Yes

在第一个样例中，数组为：$a = (1, 1, 1, 1, 1)$ 和 $b = (1, 1, 1, 1, 1)$。

• 在第一个查询中，$x = 0, y = 0$，游戏在完整数组 $a = (1, 1, 1, 1, 1)$ 和 $b = (1, 1, 1, 1, 1)$ 上进行。玩家只能在数组 $c$ 的末尾添加数字 $1$，因此游戏将在 $5$ 步后结束，鲍勃无法操作，输掉游戏。
• 在第二个查询中，$x = 0, y = 1$，游戏在数组 $a = (1, 1, 1, 1, 1)$ 和 $b = (1, 1, 1, 1)$ 上进行。游戏将在 $4$ 步后结束，爱丽丝无法操作，输掉游戏。
• 在最后一个查询中，$x = 2, y = 2$，游戏在数组 $a = (1, 1, 1)$ 和 $b = (1, 1, 1)$ 上进行。鲍勃无法操作，输掉游戏。

样例 2

输入

7 3 7 3 2 12
2 1
3 2
2 1
2 2
3 1
2 2
0 2
0 3
0 4
1 2
1 3
1 4
2 5
2 6
3 5
3 6
4 5
4 6

输出

Yes
No
Yes
Yes
No
Yes
No
Yes
No
Yes
Yes
Yes

在第二个样例中，$a = (1, 1, 2, 2, 2, 1, 1)$，$b = (2, 2, 1, 1, 1, 2, 2)$。

• 在第一个查询中，$x=0$ 和 $y = 2$，游戏在数组 $a = (1, 1, 2, 2, 2, 1, 1)$ 和 $b = (1, 1, 1, 2, 2)$ 上进行。如果爱丽丝在数组 $c$ 末尾添加数字 $2$，鲍勃也可以添加 $2$，随后没有合法操作，爱丽丝输掉。因此，爱丽丝应首先添加 $1$ 到 $c$。出于类似原因，如果鲍勃添加 $2$，他会输掉，所以他被迫添加 $1$，此时 $c = (1, 1)$。接下来爱丽丝再添加 $1$，鲍勃没有合法操作，爱丽丝获胜。
• 在第二个查询中，$x = 0$ 和 $y = 3$，游戏在数组 $a = (1, 1, 2, 2, 2, 1, 1)$ 和 $b = (1, 1, 2, 2)$ 上进行。类似前述推理，爱丽丝不能添加 $2$，否则会输掉；但如果她添加 $1$，鲍勃也会添加 $1$，随后爱丽丝因类似原因输掉。因此，鲍勃获胜。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。