AT_abc431_g.[ABC431G] One Time Swap 2

给定一个长度为 $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)$，将 $f(l,r)$ 加入 $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|})$ 和 $T = (T_1,T_2,\ldots,T_{|T|})$，我们说 $S$ 字典序小于 $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$（按数值比较）。

输入按以下格式给出：

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

每个查询的格式如下：

$k$

输出 $Q$ 行。第 $i$ 行应包含该查询的答案，格式如下：

$l\ r$

如果有多组解，输出任意一组都视为正确。

样例解释 1

$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=((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)$ 为 $(2,3)$。
• 对于第 $2$ 个询问，所有满足 $B_3=(1,2,1,2)=f(l,r)$ 的 $(l,r)$ 为 $(1,3),(2,4)$，这两组都可选。
• 对于第 $3$ 个询问，唯一满足 $B_5=(2,1,1,2)=f(l,r)$ 的 $(l,r)$ 为 $(1,2)$。

数据范围

• $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}$
• 所有输入均为整数。

由 ChatGPT 5 翻译