分数: 1800 点
问题陈述
给你正整数 N 和 K,以及两个排列 A = (A_1, A_2, \dots, A_{N+K}) 和 B = (B_1, B_2, \dots, B_{N+K}) of (1, 2, \dots, N+K).
流程 Q 查询。
对于每个查询,给定一对整数 (X, Y),解决以下问题。 (所有查询都是独立的。)
有 N + K + X 卡片标记为 1 to 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).
一开始,你有 N 卡 1 to N 在你的手中, K + X 卡来自 N+1 to N + K + X 在桌子上。
您可以执行以下操作序列任意次数,可能为零。
- 首先,选择一张手牌和一张牌桌上的牌,称之为卡牌 i 和卡 j。这里,必须满足以下条件:
- 让 (a_i, b_i) 是写在卡上的一对整数 i,和 (a_j, b_j) 是卡上的一对 j。你必须有 a_i < a_j 和 b_i < b_j.
- 然后,取出卡 j 来自桌子和位置卡 桌子上的 i (移除的卡不再可用)。
执行这些操作后,您手上至少可以持有多少张牌?
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10
- 1 \leq Q \leq 2 \times 10^5
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 \mathrm{query}_i 表示 i-第查询:
N K Q
A_1 A_2 \dots A_{N+K}
B_1 B_2 \dots B_{N+K}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询均按以下格式给出:
X Y
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i- 第一个查询。
示例输入 1
5 1 6 1 2 3 4 6 5 4 2 5 1 6 3 2 1 2 2 2 3 2 4 2 5 2 6
示例输出 1
4 3 3 3 2 1
进行查询 以 (X, Y) = (2, 2) (第二个查询)为例:
最初,你手上和桌上的牌如下:
- 你手中: (1, 4), (2, 2), (3, 5), (4, 1), (6, 6)
- 在桌子上: (5, 3), (7, 2), (8, 2)
通过执行以下操作,您可以实现最少持有三张手牌:
- 选择卡 2 在你的手中 (2, 2) 和卡 6 放在桌子上 (5, 3)。取出卡 6 来自桌子和位置卡
桌子上的 2 在桌子上。现在,还剩下以下几张牌。
- 你手中: (1, 4), (3, 5), (4, 1), (6, 6)
- 在桌子上: (2, 2), (7, 2), (8, 2)
- 选择卡 4 在你的手中 (4, 1) 和卡 8 放在桌子上 (8, 2)。取出卡 8 来自桌子和位置卡
桌子上的 4 在桌子上。现在,还剩下以下几张牌。
- 你手中: (1, 4), (3, 5), (6, 6)
- 在桌子上: (2, 2), (7, 2), (4, 1)
示例输入 2
10 2 10 12 3 2 4 10 9 5 8 1 6 11 7 3 7 2 6 10 9 1 11 5 8 4 12 2 6 3 3 1 3 1 7 1 12 3 4 3 11 2 1 2 8 1 5
示例输出 2
4 5 5 4 2 4 1 6 3 4
示例输入 3
20 3 10 18 16 5 12 21 23 14 1 19 17 3 15 13 22 7 4 2 8 9 20 6 11 10 18 1 6 20 9 13 21 17 4 16 15 22 12 14 10 23 2 5 3 19 7 11 8 1 11 1 3 3 19 1 22 2 15 4 9 3 16 1 19 5 21 2 3
示例输出 3
13 15 6 11 9 13 8 12 3 15