P15281 [MCO 2024] Max Partition

:::epigraph 从炮火中逃脱后，巨龙 Evirir 已精疲力竭，这次写不出花絮了。 ::: 给定一个正整数 $M$。有两个非负整数列表 $A_0$ 和 $A_1$，列表中的所有整数都在 $0$ 到 $M$（包含端点）之间。 你可以执行零次或多次以下操作： - 选择一个列表 $A_i$（$i = 0$ 或 $1$），并选择 $A_i$ 中的一个整数 $x$。从 $A_i$ 中移除（一个）$x$，并向 $A_{1-i}$（即另一个列表）中插入（一个）$M-x$。 **此外，在全部操作结束后，$A_0$ 和 $A_1$ 必须非空。** 列表在操作过程中可以变为空，但在 **全部** 操作结束后，两个列表都必须非空。 你想知道是否可以通过执行这些操作，使得每个列表中的最大值都等于某个特定值。你还想知道，如果添加或删除整数，答案是否会改变。 按顺序处理 $Q$ 个查询，每个查询为以下形式之一： - **类型 1 查询**： $1\ i\ x$ - 向 $A_i$ 中添加（一个）$x$。 - **类型 2 查询**： $2\ i\ x$ - 从 $A_i$ 中移除（一个）$x$。 - **类型 3 查询**： $3\ c_0\ c_1$ - 回答下列问题：是否可以在执行零次或多次操作$^1$后，使得 $\max(A_0) = c_0$ 且 $\max(A_1) = c_1$？在一行中输出 $\tt{YES}$ 或 $\tt{NO}$。 注意：对于类型 3 查询，你 **实际上并不执行任何操作**；你只需判断是否可能。 $^1$这里，$\max(A_i)$ 表示 $A_i$ 中最大的整数。

输入的第一行包含三个以空格分隔的整数 $N_0$、$N_1$ 和 $M$（$0 \le N_0, N_1 \le 2 \cdot 10^5$，$N_0 + N_1 \le 2 \cdot 10^5$，$0 \le M \le 10^9$），其中 $N_0$ 和 $N_1$ 分别是 $A_0$ 和 $A_1$ 的长度。 第二行包含 $N_0$ 个整数，即 $A_0$ 的元素。对于 $A_0$ 中的每个整数 $x$，有 $0 \le x \le M$。若 $N_0 = 0$，则该行为空行。 第三行包含 $N_1$ 个整数，即 $A_1$ 的元素。对于 $A_1$ 中的每个整数 $x$，有 $0 \le x \le M$。若 $N_1 = 0$，则该行为空行。 第四行包含一个整数 $Q$（$1 \le Q \le 2 \cdot 10^5$），表示查询的数量。 接下来的 $Q$ 行按顺序包含查询。每个查询由三个以空格分隔的整数组成，为以下形式之一： - $1\ i\ x$（$i = 0$ 或 $1$，$0 \le x \le M$） - $2\ i\ x$（$i = 0$ 或 $1$，$0 \le x \le M$） - 保证在执行此查询时，$A_i$ 中包含 $x$。 - $3\ c_0\ c_1$（$0 \le c_0, c_1 \le M$） - 保证在执行此查询时，$A_0$ 和 $A_1$ 中的整数总数至少为 $2$。 保证至少有一个类型 3 查询。

对于按顺序给出的每个类型 3 查询，如果答案为是，则在一行中输出 $\tt{YES}$，否则输出 $\tt{NO}$。 你可以以任意大小写输出 $\tt{YES}$ 和 $\tt{NO}$ 中的每个字母。例如，$\tt{yes}$ 和 $\tt{yEs}$ 将被视为 $\tt{YES}$；$\tt{no}$ 和 $\tt{No}$ 将被视为 $\tt{NO}$。

#### 注释 **示例 1** 对于第一个查询（$\tt{3 7 3}$），我们可以执行以下操作： - 从 $A_1$ 中选择 8：从 $A_1$ 中移除 8，并向 $A_0$ 中插入 $10 - 8 = 2$。 - 从 $A_1$ 中选择 7：从 $A_1$ 中移除 8，并向 $A_0$ 中插入 $10 - 7 = 3$。 操作后得到 $A_0 = [3, 4, 6, 7, 0, 2, 3]$ 和 $A_1 = [1, 3]$。$A_0$ 和 $A_1$ 中的最大元素分别如愿变为 7 和 3，因此答案为 $\tt{YES}$。 对于第四个查询（$\tt{3 4 4}$），我们可以对 $A_0$ 中的 6 和 7，以及 $A_1$ 中的 7 和 8 进行操作。操作后得到 $A_0 = [3, 4, 0, 3, 2]$ 和 $A_1 = [1, 3, 4, 3]$。 对于第五个查询（$\tt{3 7 8}$），$A_0$ 和 $A_1$ 中的最大元素已经是 7 和 8，因此无需操作。 在第六个查询（$\tt{2 1 3}$）之后，$A_1 = [1, 7, 8]$。在第七和第八个查询（$\tt{1 0 5}$ 和 $\tt{1 1 2}$）之后，$A_0 = [3, 4, 6, 7, 0, 5]$，$A_1 = [1, 7, 8, 2]$。 **示例 2** 此示例满足子任务 1 和子任务 2 的约束。对于第一个查询，我们可以移除 $A_0$ 中的一个 2，并向 $A_1$ 中插入 $8 - 2 = 6$。 **示例 3** 注意，初始时两个列表都可以为空。 #### 计分 **子任务 1** （$17$ 分）： $N_0, M, Q \le 100$。$N_1 = 0$。所有查询均为类型 3 查询，且满足 $c_0 = M - c_1$。 **子任务 2** （$9$ 分）： $N_1 = 0$。所有查询均为类型 3 查询，且满足 $c_0 = M - c_1$。 **子任务 3** （$14$ 分）： $M \le 2$。所有查询均为类型 3 查询。 **子任务 4** （$28$ 分）： $N_0 + N_1 \le 2000$，$Q \le 2000$。所有查询均为类型 3 查询。 **子任务 5** （$21$ 分）： 所有查询均为类型 3 查询。 **子任务 6** （$11$ 分）： 无额外限制。 翻译由 DeepSeek 完成