P12073 [OOI 2025] Alice, Bob, and two arrays.

[试题来源](https://inf-open.ru/2024-25/final-materials/)。

给定一个长度为 $N$ 的数组 $a$ 和一个长度为 $M$ 的数组 $b$。数组中的所有数字都是整数，且范围在 $1$ 到 $k$ 之间。还有一个初始为空的数组 $c$。 Alice 和 Bob 在这些数组上玩以下游戏：玩家轮流进行，轮到某个玩家时，他必须在数组 $c$ 的末尾追加一个数字，使得 $c$ 仍然是 $a$ 和 $b$ 共同的子序列。无法进行移动的玩家失败。Alice 先手。 他们将进行 $q$ 次游戏。对于第 $i$ 场游戏，他们会选择两个数 $x_i$ 和 $y_i$（$0 \le x_i < N，0 \le y_i < M$），然后从数组 $a$ 中移除前 $x_i$ 个元素，从数组 $b$ 中移除前 $y_i$ 个元素，接着在得到的数组上进行游戏。每次删除操作之后、下一次操作之前，数组 $a$ 和 $b$ 会恢复到它们的初始状态，这意味着在一场游戏中从数组中删除的数字可能不会在后续游戏中被删除。此外，数组 $c$ 在两场游戏之间会被清空。 这两个人有他们的怪癖，所以他们总是以这样的方式选择 $x_i$ 和 $y_i$：在删除之后，**数组 $a$ 和 $b$ 的剩余部分以相同的值开头**。 Alice 非常想赢，所以她请你判断对于每场游戏，假设双方都进行最优策略，她是否能赢。 注意，数组可能非常长，因此它们以特殊格式给出。每个数组都表示为由等值数字组成的段的序列。数组 $a$ 由 $n$ 个这样的段组成，数组 $b$ 由 $m$ 个这样的段组成。每个段由其长度和该段中的数字定义。

第一行包含六个整数 $N、n、M、m、k、q$（$1 \le N, M \le 10^9，1 \le n, m, k \le 1600，1 \le q \le 10^6$）—— 分别是第一个数组的长度、第一个数组中的段数、第二个数组的长度、第二个数组中的段数、数值上限和游戏次数。 接下来的 $n$ 行，每行包含两个整数 $l_i^a$ 和 $v_i^a$（$1 \le l_i^a \le N，1 \le v_i^a \le k$）—— 该段的长度和该段中的数字。这些数字定义了数组 $a$：数组 $a$ 的前 $l_1^a$ 个数等于 $v_1^a$，接下来的 $l_2^a$ 个数等于 $v_2^a$，……，最后 $l_n^a$ 个数等于 $v_n^a$。 接下来的 $m$ 行，每行包含两个整数 $l_i^b$ 和 $v_i^b$（$1 \le l_i^b \le N，1 \le v_i^b \le k$）—— 该段的长度和该段中的数字。这些数字定义了数组 $b$。格式与数组 $a$ 类似。保证 $\sum l_i^a = N$，$\sum l_i^b = M$，$v_i^a \ne v_{i+1}^a$ 且 $v_i^b \ne v_{i+1}^b$。 接下来的 $q$ 行包含整数对 $x_i$ 和 $y_i$（$0 \le x_i < N，0 \le y_i < M$）—— 游戏的描述。 对于每场游戏 $i$，保证如果我们从 $a$ 中移除前 $x_i$ 个元素，并从 $b$ 中移除前 $y_i$ 个元素，则数组的剩余部分将以相同的值开头。

对于 $q$ 场游戏中的每一场，如果 Alice 在最优策略下获胜，则打印 `Yes`，如果 Bob 获胜，则打印 `No`。

**样例解释** 在第一个示例中，数组看起来像这样：$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)$ 上进行。在这种情况下，玩家只能将数字 $1$ 追加到数组 $c$ 中，因此 5 步之后游戏将结束，Bob 将会失败，因为他无法再进行移动。 * 在第二个查询中，$x = 0，y = 1$，因此游戏将在数组 $a = (1, 1, 1, 1, 1)$ 和 $b = (1, 1, 1, 1)$ 上进行。在这种情况下，游戏将在 4 步之后结束，Alice 将会失败。 * 在最后一个查询中，$x = 2，y = 2$，因此游戏将在数组 $a = (1, 1, 1)$ 和 $b = (1, 1, 1)$ 上进行。在这种情况下，Bob 将会失败。 在第二个示例中，$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)$ 上进行。如果 Alice 将数字 $2$ 追加到数组 $c$ 中，Bob 也会追加数字 $2$，然后就没有移动机会了，所以 Alice 会失败。因此，Alice 必须首先将数字 $1$ 追加到 $c$。此后，出于类似的原因，如果 Bob 将数字 $2$ 追加到数组中，他将会失败。所以，他被迫追加数字 $1$，数组 $c$ 变为 $(1, 1)$。然后 Alice 再次将数字 $1$ 追加到数组 $c$ 中，Bob 没有更多移动机会了，所以 Alice 获胜。 * 在第二个查询中，$x = 0$ 且 $y = 3$，因此游戏将在数组 $a = (1, 1, 2, 2, 2, 1, 1)$ 和 $b = (1, 1, 1, 2, 2)$ 上进行。根据上一个示例的推理，Alice 不能将数字 $2$ 追加到数组 $c$ 中，因为那样她会失败。但是如果 Alice 追加数字 $1$，那么 Bob 也会追加数字 $1$，之后，Alice 会因为类似的原因而失败。因此，在这种情况下 Bob 获胜。 **评分** 本题的测试点包含十一个分组。每个分组的分数只有在该分组的所有测试点以及所有依赖分组的测试点都通过时才能获得。请注意，通过样例测试点对于某些分组不是必需的。Offline-evaluation 表示该分组的测试结果将在比赛结束后才可查看。 | Subtask | 分数 | 额外限制 | | | 依赖组别 | 说明 | | :--- | :--- | :------------------- | :---------- | :---------- | :------- | :------------------------------------------------------------------------------------------------------------------------------------ | | | | $N, M$ | $n, m$ | $q$ | | | | 0 | 0 | - | - | - | - | 样例。 | | 1 | 13 | $N, M \le 300$ | - | $q \le 10^5$ | 0 | | | 2 | 12 | $N, M \le 5000$ | - | $q \le 10^5$ | 0, 1 | | | 3 | 11 | - | - | $q \le 10^5$ | - | $l_i^a \le 1000$ 且所有 $v_i^a$ 不同，$l_i^b \le 1000$ 且所有 $v_i^b$ 不同 | | 4 | 8 | - | - | $q \le 10^5$ | 3 | $l_i^a \le 1000$ 且所有 $v_i^a$ 不同 | | 5 | 10 | - | - | $q \le 10^5$ | - | $l_1^a \ge N - 500$ 且 $v_1^a = 1$，$l_1^b \ge M - 500$ 且 $v_1^b = 1$ | | 6 | 7 | $N, M \le 10^5$ | $n, m \le 100$ | $q \le 10^5$ | - | $k \le 5$ | | 7 | 6 | $N, M \le 10^5$ | $n, m \le 100$ | $q \le 10^5$ | 0, 6 | $k \le 50$ | | 8 | 7 | - | $n, m \le 100$ | $q \le 10^5$ | 0, 6, 7 | $k \le 50$ | | 9 | 9 | - | $n, m \le 800$ | $q \le 10^5$ | 0, 6 - 8 | | | 10 | 10 | - | - | $q \le 10^5$ | 0 - 9 | Offline-evaluation。 | | 11 | 7 | - | - | - | 0 - 10 | Offline-evaluation。 |