D - 2D Solitaire Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1800 点

問題文

正整数 N, K および (1, 2, \dots, 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 枚のカードがあります。
各カードには整数の組が書かれていて、カード i には

  • 1 \leq i \leq N+K の時、(A_i, B_i)
  • N + K + 1 \leq i \leq N + K + X の時、(i, Y)

が書かれています。

今、あなたはカード 1 からカード N までの N 枚のカードを持っています。また、場にカード N+1 からカード N+K+X までの K+X 枚のカードが場に置かれています。
あなたは次の一連の操作を 0 回以上自由な回数行うことが出来ます。

  • まず、持っているカードと場に置かれているカードを 1 枚ずつ選び、それぞれカード i、カード j とする。ただし、選んだカードは次の条件を満たす必要がある。
    • カード i に書かれている整数の組を (a_i, b_i)、カード j に書かれている整数の組を (a_j, b_j) とした時、a_i \lt a_j かつ b_i \lt 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

2 番目のクエリ、すなわち (X, Y) = (2, 2) の場合を例に挙げて説明します。
はじめ、持っているカードと場に出ているカードを列挙すると次のようになります。

  • 持っているカード : (1, 4), (2, 2), (3, 5), (4, 1), (6, 6)
  • 場に出ているカード : (5, 3), (7, 2), (8, 2)

この時、次のように操作を行うことで持っているカードの枚数を 3 枚にすることができて、これが最小です。

  • 持っているカードとして (2, 2) が書かれたカード 2 を、場に出ているカードとして (5, 3) が書かれたカード 6 を選ぶ。カード 6 を場から取り除き、カード 2 を場に置く。取り除かれていないカードの状況は次のようになる。
    • 持っているカード : (1, 4), (3, 5), (4, 1), (6, 6)
    • 場に出ているカード : (2, 2), (7, 2), (8, 2)
  • 持っているカードとして (4, 1) が書かれたカード 4 を、場に出ているカードとして (8, 2) が書かれたカード 8 を選ぶ。カード 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

Score : 1800 points

Problem Statement

You are given positive integers N and K, and two permutations A = (A_1, A_2, \dots, A_{N+K}) and B = (B_1, B_2, \dots, B_{N+K}) of (1, 2, \dots, N+K).
Process Q queries.

For each query, given a pair of integers (X, Y), solve the following problem. (All queries are independent.)

There are N + K + X cards labeled from 1 to N + K + X.
Each card has a pair of integers written on it. Specifically,

  • For 1 \leq i \leq N+K, card i has (A_i, B_i).
  • For N + K + 1 \leq i \leq N + K + X, card i has (i, Y).

At the beginning, you have the N cards 1 to N in your hand, and the K + X cards from N+1 to N + K + X are on the table.
You may perform the following sequence of operations any number of times, possibly zero.

  • First, choose one card from your hand and one card from the table, calling them card i and card j. Here, the following condition must hold:
    • Let (a_i, b_i) be the pair of integers written on card i, and (a_j, b_j) be the pair on card j. You must have a_i < a_j and b_i < b_j.
  • Then, remove card j from the table and place card i on the table (the removed card is no longer available).

What is the minimum number of cards you can end up holding in your hand after performing these operations?

Constraints

  • 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 and B are permutations of (1, 2, \dots, N+K).
  • 1 \leq X \leq 10
  • 1 \leq Y \leq N + K
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{query}_i denotes the i-th query:

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

Each query is given in the following format:

X Y

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 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

Sample Output 1

4
3
3
3
2
1

Taking the query (X, Y) = (2, 2) (the second query) as an example:

Initially, the cards in your hand and on the table are as follows:

  • In your hand: (1, 4), (2, 2), (3, 5), (4, 1), (6, 6)
  • On the table: (5, 3), (7, 2), (8, 2)

You can achieve holding three cards in your hand, which is the minimum, by performing the following operations:

  • Choose card 2 in your hand with (2, 2) and card 6 on the table with (5, 3). Remove card 6 from the table and place card 2 on the table. Now, the following cards are remaining.
    • In your hand: (1, 4), (3, 5), (4, 1), (6, 6)
    • On the table: (2, 2), (7, 2), (8, 2)
  • Choose card 4 in your hand with (4, 1) and card 8 on the table with (8, 2). Remove card 8 from the table and place card 4 on the table. Now, the following cards are remaining.
    • In your hand: (1, 4), (3, 5), (6, 6)
    • On the table: (2, 2), (7, 2), (4, 1)

Sample Input 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

Sample Output 2

4
5
5
4
2
4
1
6
3
4

Sample Input 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

Sample Output 3

13
15
6
11
9
13
8
12
3
15