AT_abc253_g [ABC253G] Swap Many Times

题目描述

对于 $2$ 以上的整数 $N$，满足 $1 \leq x < y \leq N$ 的整数对 $(x, y)$ 一共有 $\frac{N(N-1)}{2}$ 个。

将这些整数对按字典序从小到大排列后，第 $L$ 个、第 $L+1$ 个、$\ldots$、第 $R$ 个分别记作 $(x_1, y_1), \dots, (x_{R-L+1}, y_{R-L+1})$。对于数列 $A = (1, 2, \dots, N)$，依次对 $i = 1, \dots, R-L+1$ 执行以下操作：

• 交换 $A_{x_i}$ 和 $A_{y_i}$。

请输出所有操作结束后得到的 $A$。

此外，$(a, b)$ 在字典序上小于 $(c, d)$，当且仅当以下任一条件成立：

• $a < c$
• $a = c$ 且 $b < d$

输入格式

输入从标准输入中给出，格式如下：

$N$ $L$ $R$

输出格式

请输出操作结束后 $A$ 的所有元素，用空格分隔，输出一行。

输入输出样例 #1

输入 #1

5 3 6

输出 #1

5 1 2 3 4

输入输出样例 #2

输入 #2

10 12 36

输出 #2

1 10 9 8 7 4 3 2 5 6

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq L \leq R \leq \frac{N(N-1)}{2}$
• 输入均为整数

样例解释 1

满足 $1 \leq x < y \leq N$ 的整数对按字典序排列后，第 $3, 4, 5, 6$ 个分别为 $(1, 4), (1, 5), (2, 3), (2, 4)$。依次进行操作后，$A$ 的变化如下：

$(1, 2, 3, 4, 5) \rightarrow (4, 2, 3, 1, 5) \rightarrow (5, 2, 3, 1, 4) \rightarrow (5, 3, 2, 1, 4) \rightarrow (5, 1, 2, 3, 4)$。

由 ChatGPT 4.1 翻译