/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
2 以上の整数 N に対し、1 \leq x \lt 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, \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, 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)
入力例 2
10 12 36
出力例 2
1 10 9 8 7 4 3 2 5 6
Score : 600 points
Problem Statement
For an integer N greater than or equal to 2, there are \frac{N(N - 1)}{2} pairs of integers (x, y) such that 1 \leq x \lt y \leq N.
Consider the sequence of these pairs sorted in the increasing lexicographical order. Let (x_1, y_1), \dots, (x_{R - L + 1}, y_{R - L + 1}) be its L-th, (L+1)-th, \ldots, and R-th elements, respectively. On a sequence A = (1, \dots, N), We will perform the following operation for i = 1, \dots, R-L+1 in this order:
- Swap A_{x_i} and A_{y_i}.
Find the final A after all the operations.
We say that (a, b) is smaller than (c, d) in the lexicographical order if and only if one of the following holds:
- a \lt c
- a = c and b \lt d
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq L \leq R \leq \frac{N(N-1)}{2}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N L R
Output
Print the terms of A after all the operations in one line, separated by spaces.
Sample Input 1
5 3 6
Sample Output 1
5 1 2 3 4
Consider the sequence of pairs of integers such that 1 \leq x \lt y \leq N sorted in the increasing lexicographical order. Its 3-rd, 4-th, 5-th, and 6-th elements are (1, 4), (1, 5), (2, 3), (2, 4), respectively.
Corresponding to these pairs, A transitions as follows.
(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)
Sample Input 2
10 12 36
Sample Output 2
1 10 9 8 7 4 3 2 5 6