N - Swap and Sort Editorial /

Time Limit: 3.5 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

長さ N の数列 a_1, a_2, \ldots, a_N があります。 最初、a_i = i です。

この数列に対するクエリが Q 個与えられます。

i 番目のクエリの内容は t_i, x_i, y_i の 3 つの整数によって表され、その意味は以下の通りです。

  • t_i = 1 のとき、a_{x_i} と a_{x_i + 1} をスワップする
  • t_i = 2 のとき、a_{x_i}, a_{x_i + 1}, \ldots a_{y_i} を昇順に並べ替える

全てのクエリを順番に処理したあとの数列 a を出力してください。

制約

  • 入力は全て整数である。
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • t_i は 1 または 2 である。
  • t_i = 1 のとき、1 \leq x_i < N かつ y_i = 0 が成り立つ。
  • t_i = 2 のとき、1 \leq x_i < y_i \leq N が成り立つ。

入力

入力は以下の形式で標準入力から与えられる。

N Q
t_1 x_1 y_1
t_2 x_2 y_2
\vdots
t_Q x_Q y_Q

出力

全てのクエリを順番に処理したあとの a の要素を空白区切りで出力せよ。

入力例 1

5 3
1 1 0
1 2 0
2 2 4

出力例 1

2 1 3 4 5
  • 1 番目のクエリを処理すると a は 2, 1, 3, 4, 5 になります。
  • 2 番目のクエリを処理すると a は 2, 3, 1, 4, 5 になります。
  • 3 番目のクエリを処理すると a は 2, 1, 3, 4, 5 になります。

入力例 2

10 15
1 3 0
1 5 0
1 4 0
1 2 0
1 3 0
2 4 7
1 5 0
1 7 0
1 9 0
1 8 0
2 3 5
1 8 0
1 9 0
1 5 0
1 2 0

出力例 2

1 2 4 5 3 6 8 7 9 10

Score : 6 points

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a sequence of length N: a_1, a_2, \ldots, a_N. Initially, a_i = i.

You will be given Q queries regarding this sequence.

The i-th query will be described by three integers t_i, x_i, and y_i, as follows:

  • if t_i = 1, swap a_{x_i} and a_{x_i + 1};
  • if t_i = 2, rearrange a_{x_i}, a_{x_i + 1}, \ldots a_{y_i} in ascending order.

Print the sequence a after all the queries are processed in order.

Constraints

  • All values in input are integers.
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • t_i is 1 or 2.
  • If t_i = 1, then 1 \leq x_i < N and y_i = 0.
  • If t_i = 2, then 1 \leq x_i < y_i \leq N.

Input

Input is given from Standard Input in the following format:

N Q
t_1 x_1 y_1
t_2 x_2 y_2
\vdots
t_Q x_Q y_Q

Output

Print the elements of a after all the queries are processed in order, with space in between.

Sample Input 1

5 3
1 1 0
1 2 0
2 2 4

Sample Output 1

2 1 3 4 5
  • After the first query is processed, a is 2, 1, 3, 4, 5.
  • After the second query is processed, a is 2, 3, 1, 4, 5.
  • After the third query is processed, a is 2, 1, 3, 4, 5.

Sample Input 2

10 15
1 3 0
1 5 0
1 4 0
1 2 0
1 3 0
2 4 7
1 5 0
1 7 0
1 9 0
1 8 0
2 3 5
1 8 0
1 9 0
1 5 0
1 2 0

Sample Output 2

1 2 4 5 3 6 8 7 9 10