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 翻译