当前没有测试数据。

G - 交换多次

得分：$600$ 点

问题描述

对于一个大于等于2的整数$N$，存在$\frac{N(N - 1)}{2}$个整数对$(x, y)$，满足$1 \leq x \lt y \leq N$。

考虑将这些整数对按照字典序递增的顺序排序。设它们的$L$-th, $(L+1)$-th, $\ldots$到$R$-th的元素分别是$(x_1, y_1), \dots, (x_{R - L + 1}, y_{R - L + 1})$。在序列$A = (1, \dots, N)$上，我们按照以下顺序执行操作，对于每个$i = 1, \dots, R-L+1$：

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

找到所有操作执行完毕之后的最终$A$序列。

我们说，在字典序中，$(a, b)$小于$(c, d)$当且仅当以下条件之一满足：

• $a \lt c$
• $a = c$且$b \lt d$

约束

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq L \leq R \leq \frac{N(N-1)}{2}$
• 输入中的所有值都是整数。

输入

从标准输入中按以下格式给出：

$N$ $L$ $R$

输出

在一行中按照空格分隔打印出所有操作执行完毕后的$A$序列。

5 3 6

5 1 2 3 4

考虑将整数对按照$1 \leq x \lt 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)$

10 12 36

1 10 9 8 7 4 3 2 5 6