130. Day 1 PH. 排隊問題

排隊問題

題目敘述

• 一開始有$n$個人，編號為$1\sim n$，總共有$n$個隊伍，編號也是$1\sim n$。現在讓編號$1$的人排在編號$1$的隊伍、編號$2$的人排在編號$2$的隊伍...編號$n$的人排在編號$n$的隊伍。接著有$m$個指令，必須按先輸入後順序執行，指令有三種，分別是0 a b、1 a b和2 a b，三種指令解說如下:

  • 0 a b
    表示編號$a$的人從原來的位置離開，排到編號$b$的人的後面
  • 1 a b
    表示編號$a$的隊伍的所有人，按原來順序排到編號$b$的隊伍的尾端，注意編號$a$的隊伍和編號$b$的隊伍都有可能沒人排隊
  • 2 a b
    表示編號$a$的隊伍的第一個人，排到編號$b$的隊伍的尾端(如果編號$a$的隊伍有人的話)，注意編號$a$的隊伍和編號$b$的隊伍都有可能沒人排隊

• 請你在所有操作都完成後，按順序輸出每一隊的人。

輸入說明

• 第一行有兩個整數$n(1 \leq n \leq 10^6),m(1 \leq m \leq 2*10^6)$

• 接著有m行，每行有三個整數$t~a~b$為輸入的指令

$t = 0 , 1 , 2$
$1 \leq a,b \leq n$
對於$t=0$和$t=1$，保證$a \neq b$

輸出說明

• 按照順序輸出每一隊在所有操作都完成後的情況，行尾不能有空白，詳見範例輸入輸出。

範例輸入

6 5
0 4 3
0 6 5
1 2 5
1 6 5
2 5 4

範例輸出

#1: 1
#2:
#3: 3 4
#4: 5
#5: 6 2
#6:

配分方法

• 10% $n \leq 100$
• 20% $n \leq 1000$
• 30% $n \leq 10^4$
• 40% $n \leq 10^6$

Hints

• 實作linked list

備註

關於範例測資，一開始的時候長這樣:

#1: 1
#2: 2
#3: 3
#4: 4
#5: 5
#6: 6

第一次操作:

#1: 1
#2: 2
#3: 3 4
#4:
#5: 5
#6: 6

第二次操作:

#1: 1
#2: 2
#3: 3 4
#4:
#5: 5 6
#6:

第三次操作:

#1: 1
#2:
#3: 3 4
#4:
#5: 5 6 2
#6:

第四次操作:

#1: 1
#2:
#3: 3 4
#4:
#5: 5 6 2
#6:

第五次操作:

#1: 1
#2:
#3: 3 4
#4: 5
#5: 6 2
#6:

Judge Setting

run-time limit: 1200 ms
memory limit: 6553600 byte
測資數量: 0