← 返回题目列表

AtCoder · agc070_d

D. 2D 纸牌

中文机器翻译题面 查看原题

分数: 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