← 返回题目列表

AtCoder · abc253_g

G. 多次交换

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

对于整数 N 大于或等于 2,有 \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-th, (L+1)-th, \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

约束

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

输入

输入由标准输入按以下格式给出:

N L R

输出

打印条款 A 所有操作在一行之后,以空格分隔。


示例输入 1

5 3 6

示例输出 1

5 1 2 3 4

考虑整数对的序列,使得 1 \leq x \lt y \leq N 按字典顺序升序排序。 其 3-rd, 4-th, 5-th,以及 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)


示例输入 2

10 12 36

示例输出 2

1 10 9 8 7 4 3 2 5 6