← 返回题目列表

AtCoder · abc431_g

G. 一次性交换 2

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

分数: {575} 点

问题陈述

给你一个整数序列 给出了 A=(A_1,A_2,\ldots,A_N) 长度 N.

对于一对整数 (l, r) \ (1\leq l\lt r\leq N),让 f(l,r) 是通过交换得到的整数序列 l第一个元素和 r- 第一个元素 A.

生成整数序列的序列 B=(B_1,B_2,\ldots,B_{\frac{N(N-1)}{2}}) 长度 \frac{N(N-1)}{2} 通过以下程序:

  • 准备一个空序列 B=().
  • 对于每对整数 (l, r)\ (1\leq l\lt r\leq N),添加 f(l,r) to B.
  • 排序 B 按序列的字典顺序排列。

你被给予 Q 查询;按顺序处理它们。的 i第查询如下:

  • 给定一个整数 k,找到一对整数 (l, r) \ (1\leq l\lt r\leq N) 这样 B_k=f(l,r) 并输出。
序列的字典顺序是什么?

一个序列 S = (S_1,S_2,\ldots,S_{|S|}) is 按字典顺序较小 比序列 T = (T_1,T_2,\ldots,T_{|T|}) 当且仅当以下两个条件之一成立时。 在这里, |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 使得以下两者成立:
    • (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).

序列 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-st查询,唯一 (l,r) 这样 B_1=(1,1,2,2)=f(l,r) is (l,r)=(2,3).
  • 对于 2-nd 查询, (l,r) 这样 B_3=(1,2,1,2)=f(l,r) 是 (l,r)=(1,3),(2,4)。在这种情况下,任何一个都将被认为是正确的。
  • 对于 3-rd查询,唯一 (l,r) 这样 B_5=(2,1,1,2)=f(l,r) is (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