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 自动生成**