G - One Time Swap 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : {575} 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

整数の組 (l, r) \ (1\leq l\lt r\leq N) に対し、f(l,r) を「A の l 番目の要素と r 番目の要素を入れ替えることで得られる整数列」とします。

長さ \frac{N(N-1)}{2} の整数列の列 B=(B_1,B_2,\ldots,B_{\frac{N(N-1)}{2}}) を次の手順で生成します。

  • 空の列 B=() を用意する。
  • 各整数の組 (l, r)\ (1\leq l\lt r\leq N) に対し、B に f(l,r) を追加する。
  • B を数列の辞書順でソートする。

Q 個のクエリが与えられるので、順に処理してください。i 番目のクエリは以下の通りです。

  • 整数 k が与えられる。B_k=f(l,r) となるような整数の組 (l, r) \ (1\leq l\lt r\leq N) を一つ求めそれを出力せよ。
数列の辞書順とは？

数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、|S|, |T| はそれぞれ S, T の長さを表します。

  1. |S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})。
  2. ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
    • (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
    • S_i が T_i より（数として）小さい。

制約

  • 2\leq N\leq 2\times 10^5
  • 1\leq Q\leq 2\times 10^5
  • 1\leq A_i\leq N
  • 1\leq k\leq \frac{N(N-1)}{2}
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下の形式で与えられる。

k

出力

Q 行出力せよ。i 行目には、i 番目のクエリに対する答えを以下の形式で出力せよ。

l r

答えが複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

4 3
1 2 1 2
1
3
5

出力例 1

2 3
2 4
1 2

f(1, 2) = (2, 1, 1, 2), f(1, 3) = (1, 2, 1, 2), f(1, 4) = (2, 2, 1, 1), f(2, 3) = (1, 1, 2, 2), f(2, 4) = (1, 2, 1, 2), f(3, 4) = (1, 2, 2, 1) です。

これら 6 つの数列を辞書順でソートした列 B は B=((1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 2, 1, 1)) です。

  • 1 番目のクエリについて、B_1=(1,1,2,2)=f(l,r) が成り立つような (l,r) は (l,r)=(2,3) のみです。
  • 2 番目のクエリについて、B_3=(1,2,1,2)=f(l,r) が成り立つような (l,r) は (l,r)=(1,3),(2,4) です。この場合、どちらを出力しても正解とみなされます。
  • 3 番目のクエリについて、B_5=(2,1,1,2)=f(l,r) が成り立つような (l,r) は (l,r)=(1,2) のみです。

入力例 2

10 10
1 1 2 7 6 3 5 7 3 3
21
36
9
17
13
24
7
45
33
1

出力例 2

6 8
2 4
5 7
9 10
8 9
3 9
5 9
1 8
2 10
4 10

Score : {575} points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

For a pair of integers (l, r) \ (1\leq l\lt r\leq N), let f(l,r) be the integer sequence obtained by swapping the l-th element and the r-th element of A.

Generate a sequence of integer sequences B=(B_1,B_2,\ldots,B_{\frac{N(N-1)}{2}}) of length \frac{N(N-1)}{2} by the following procedure:

  • Prepare an empty sequence B=().
  • For each pair of integers (l, r)\ (1\leq l\lt r\leq N), add f(l,r) to B.
  • Sort B in lexicographical order of sequences.

You are given Q queries; process them in order. The i-th query is as follows:

  • Given an integer k, find one pair of integers (l, r) \ (1\leq l\lt r\leq N) such that B_k=f(l,r) and output it.
What is lexicographical order of sequences?

A sequence S = (S_1,S_2,\ldots,S_{|S|}) is lexicographically smaller than a sequence T = (T_1,T_2,\ldots,T_{|T|}) if and only if one of the following two conditions holds. Here, |S| and |T| represent the lengths of S and T, respectively.

  1. |S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
  2. There exists an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace such that both of the following hold:
    • (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
    • S_i is smaller than T_i (as a number).

Constraints

  • 2\leq N\leq 2\times 10^5
  • 1\leq Q\leq 2\times 10^5
  • 1\leq A_i\leq N
  • 1\leq k\leq \frac{N(N-1)}{2}
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

k

Output

Output Q lines. The i-th line should contain the answer to the i-th query in the following format:

l r

If there are multiple solutions, any of them will be considered correct.

Sample Input 1

4 3
1 2 1 2
1
3
5

Sample Output 1

2 3
2 4
1 2

f(1, 2) = (2, 1, 1, 2), f(1, 3) = (1, 2, 1, 2), f(1, 4) = (2, 2, 1, 1), f(2, 3) = (1, 1, 2, 2), f(2, 4) = (1, 2, 1, 2), f(3, 4) = (1, 2, 2, 1).

The sequence B obtained by sorting these six sequences in lexicographical order is B=((1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 2, 1, 1)).

  • For the 1-st query, the only (l,r) such that B_1=(1,1,2,2)=f(l,r) is (l,r)=(2,3).
  • For the 2-nd query, (l,r) such that B_3=(1,2,1,2)=f(l,r) are (l,r)=(1,3),(2,4). In this case, either one will be considered correct.
  • For the 3-rd query, the only (l,r) such that B_5=(2,1,1,2)=f(l,r) is (l,r)=(1,2).

Sample Input 2

10 10
1 1 2 7 6 3 5 7 3 3
21
36
9
17
13
24
7
45
33
1

Sample Output 2

6 8
2 4
5 7
9 10
8 9
3 9
5 9
1 8
2 10
4 10