40007. Practice 7: 中國隊列問題

I'm a slow walker, but I never walk backwards.

中國有許多獨特的傳統,如鼎鼎大名的「中國洗衣問題」就曾經讓許多人百思不得其解。除了中國洗衣問題以外,「中國隊列」也是一個印證中國人超群智慧的文化。

「中國隊列」可以描述如下:假設今天有$N$個中國人,分別編號為1到N,將這些人稱為$p_1, p_2,\cdots, p_{N}$。若這些中國人要排成一個隊列,則他們會按照編號$a_1,a_2,\cdots ,a_{N}$的順序一個一個進入隊列:$p_{a_1}$會先進入隊列,接下來$p_{a_i}$進入時,他會找$p_{a_1},p_{a_2},\cdots ,p_{a_{i-1}}$中任一個人,排在他的前或後方。這種隊列我們稱之為「中國隊列」。 中國隊列並不是一成不變的。在形成隊列過程中可能會發生人群的「重組」現象:對於已經在隊列裡的一群人,他們互相討論好之後,可以一起按照原先的順序移動到另一個也在隊列中的人的前面。「重組」現象是中國隊列的精髓所在,必須要有強大的合作精神才有可能做到大規模的重組。 例如,一開始隊列由前到後依序是$p_4, p_9, p_3, p_1, p_5, p_8$,若$p_5$前面、$p_3$後面的所有人(也就是$p_1, p_3, p_5$三人)討論好要移動到$p_4$前面的話,重組後的隊列就會變成$p_3, p_1, p_5, p_4, p_9, p_8$。

某日一群中國人準備要排成中國隊列領取訂購的商品。很恰好地,他們買的商品都是某種食物,並且每個人都只買了一個。 這個店家知道中國文化的精妙之處,因此決定使用以下的策略發放商品:他們每生產一批$B$個商品之後,就會在當前的隊列中選定一個人$A$,並且從$A$開始一個一個往隊列的前方或後方發(往排在最前面的人的方向稱為前方),一直到$B$個商品都發放完畢為止。拿到商品的人就會直接離開隊列。如果發到隊列的末端還沒把$B$個商品發完的話,剩餘的那些就視為作廢。為了不造成混亂,店家會在完成這批商品的發放之後才允許其他人進入隊列。

給定一個中國隊列形成、重組與商品發放的過程,請你求出所有中國人拿到商品的順序,以及這個店家總共作廢了幾個商品。

Input/Output

第一行有一個正整數$T$,代表測資筆數。 接下來每一筆測資中,第一行有三個非負整數$N,M,a_1$,分別代表要進入隊列的中國人的數量、總共發生了幾個事件與第一個進入隊列的中國人編號。(進入隊列、重組、發放商品都稱為事件,但是第一個進入隊列不算一次事件。)

接下來有$M$行,每行有四個正整數K, A, B, C,其中$K\leq 3$且$A,B,C\leq N$。 如果K=1,則$C\leq 2$,代表$p_A$進入隊列。如果C=1,代表他排在$p_B$的前面;如果C=2,代表他排在$p_B$的後面。保證$p_A$未曾進入隊列,且$p_B$正在隊列當中。 如果K=2,代表一次重組,排在$p_A$後面且在$p_B$前面的所有人,都移動到$p_C$前面。保證$p_A, p_B, p_C$都正在隊列當中,並且$A=B$或者$p_A$排在$p_B$的前面,且$p_C$不在$p_A$和$p_B$之間。 如果K=3,則$B \geq 1, C\leq 2$,代表店家從$p_A$開始發放B個商品。如果C=1,代表往前方發放商品;如果C=2,代表往後方發放商品。保證$p_A$正在隊列當中,且除了最後一次發放商品以外,發放完商品的時候必定還有人在隊列中。

對於每筆測資,請輸出$N+1$行,每行有一個非負整數。 第一行請輸出店家總共作廢了幾個商品。接下來$N$行請由最先到最後的順序輸出拿到商品的中國人編號。

Subtasks/Constraints

所有測資皆符合: $T\leq 5; a_1\leq N\lt M\leq 2\times 10^ 6$;保證整個過程結束後,所有中國人都有拿到商品。

  1. $M\leq 10^ 4$ (15 pts)
  2. $M\leq 10^ 5$ (25 pts)
  3. 不會有重組;進入隊列只會從最前端或最尾端進入;發放商品的起點必定在最前端或最後端 (15 pts)
  4. 無額外限制 (45 pts)

Sample Input

1
6 10 5
1 3 5 2
1 6 5 2
1 2 3 1
2 2 2 6
3 3 5 2
1 4 2 2
1 1 4 1
2 1 6 5
3 1 5 1
3 4 5 2

Sample Output

9
3
1
4
6
5
2

範例測資中,隊列的變化如下(左邊為前,右邊為後):

5
5 3
5 6 3
5 6 2 3
5 2 6 3
5 2 6
5 2 4 6
5 2 1 4 6
1 4 6 5 2
4 6 5 2
*

Discussion