AT_agc070_d.[AGC070D] 2D Solitaire

给定正整数 $N$ 和 $K$，还有两个排列 $A=(A_1, A_2, \dots, A_{N+K})$ 和 $B=(B_1, B_2, \dots, B_{N+K})$。你需要处理 $Q$ 个独立的查询。

每个查询都会给出一个整数对 $(X, Y)$，你的任务是解决以下问题：

假设有从编号 $1$ 到 $N + K + X$ 的 $N + K + X$ 张卡牌，其中每张卡牌上都有一个整数对：

• 对于 $1 \leq i \leq N+K$，卡牌 $i$ 上的整数对为 $(A_i, B_i)$；
• 对于 $N + K + 1 \leq i \leq N + K + X$，卡牌 $i$ 上的整数对为 $(i, Y)$。

你一开始持有编号 $1$ 到 $N$ 的 $N$ 张卡牌，而编号从 $N+1$ 到 $N+K+X$ 的 $K+X$ 张卡牌放在场上。

你可以进行以下操作任意次数：

• 从持有的卡牌中选一张卡片 $i$，从场上选一张卡片 $j$，两个卡片编号需满足以下条件：
  • 持有的卡片 $i$ 上的整数对是 $(a_i, b_i)$，场上的卡片 $j$ 上的整数对是 $(a_j, b_j)$，并且 $a_i < a_j$ 且 $b_i < b_j$。
• 然后，移除场上的卡片 $j$，将卡片 $i$ 放到场上。（移除的卡片不能再使用。）

你需要通过上述操作，使持有的卡片数量达到最少，最少能达到多少？

输入包含一行，按以下格式给出：

$N\ K\ Q\ A_1\ A_2\ \ldots\ A_{N+K}\ B_1\ B_2\ \ldots\ B_{N+K}\ \text{查询}_1\ \text{查询}_2\ \ldots\ \text{查询}_Q$

每个查询的格式如下：

$X\ Y$

输出 $Q$ 行，每行一个整数，第 $i$ 行表示第 $i$ 个查询的答案。

• $1 \leq N \leq 200,000$
• $1 \leq K \leq 10$
• $1 \leq Q \leq 200,000$
• $1 \leq A_i \leq N + K$
• $1 \leq B_i \leq N + K$
• $A$ 和 $B$ 都是 $(1, 2, \dots, N+K)$ 的排列
• $1 \leq X \leq 10$
• $1 \leq Y \leq N + K$
• 所有输入均为整数

示例解释

以第二个查询 $(X, Y) = (2, 2)$ 为例：

• 初始持有的卡片为：$(1, 4), (2, 2), (3, 5), (4, 1), (6, 6)$
• 场上的卡牌为：$(5, 3), (7, 2), (8, 2)$

通过以下操作，可将持有的卡牌减少到 $3$ 张，且不能再少：

• 选择持有的卡片 $(2, 2)$ 和场上的卡片 $(5, 3)$，执行操作后：

  • 持有的卡片变为：$(1, 4), (3, 5), (4, 1), (6, 6)$
  • 场上的卡片变为：$(2, 2), (7, 2), (8, 2)$

• 再选择持有的卡片 $(4, 1)$ 和场上的卡片 $(8, 2)$，执行操作后：

  • 持有的卡片变为：$(1, 4), (3, 5), (6, 6)$
  • 场上的卡片变为：$(2, 2), (7, 2), (4, 1)$

本翻译由 AI 自动生成