Swap Many Times

题目描述

对于一个大于或等于 $2$ 的整数 $N$，存在 $\frac{N(N - 1)}{2}$ 个整数对 $(x, y)$ 满足 $1 \leq x \lt y \leq N$。 考虑按字典序升序排列的这些对的序列。 令 $(x_1, y_1), \dots, (x_{R - L + 1}, y_{R - L + 1})$ 分别为该序列的第 $L$ 项、第 $(L+1)$ 项、$\ldots$、第 $R$ 项。在序列 $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$

输入格式

输入按以下格式由标准输入给出： $N$ $L$ $R$

输出格式

在一行中按空格分隔输出所有操作结束后的 $A$ 的各项。

5 3 6

5 1 2 3 4

10 12 36

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 \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)$

标签: AtCoder|abc253G

来源

AtCoder|abc253G