102536: [AtCoder]ABC253 G - Swap Many Times
Description
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
Input
题意翻译
### 题意 你有一个长度为 $n$ 的序列 $a$，初始时，对于每一个 $i(1\le i\le n)$，满足 $a_i=i$。 然后你可以根据 $n$ 构造出一个长度为 $\frac{n(n-1)}{2}$ 的二元组序列，包含满足 $1\le l<r\le n$ 的所有二元组 $(l,r)$。并且将得到的序列以 $l$ 为第一关键字，$r$ 为第二关键字由小到大排序。 例如，当 $n=4$，时，二元组序列为： $$(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$$ 定义一个二元组 $(l,r)$ 对应的操作为交换 $a_l$ 和 $a_r$。 给出一个 $L$ 和一个 $R$，要求你求出在执行完第 $L$ 个到第 $R$ 个二元组所对应的操作后的序列。 ### 样例解释 - 样例 1： $n=5$ 时，第 $3$ 个到第 $6$ 个二元组为: $$(1,4),(1,5),(2,3),(2,4)$$ 所以执行完操作后原序列变为： $$1,2,3,4,5 \longrightarrow 5,1,2,3,4$$Output
问题描述
对于大于或等于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$
约束
- $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