1930 . 中國隊列問題
TopCoder
Tags
Description
中國有許多獨特的傳統，如鼎鼎大名的「中國洗衣問題」就曾經讓許多人百思不得其解。除了中國洗衣問題以外，「中國隊列」也是一個印證中國人超群智慧的文化。
「中國隊列」可以描述如下：假設今天有$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 Format
第一行有一個正整數$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$正在隊列當中，且除了最後一次發放商品以外，發放完商品的時候必定還有人在隊列中。
保證整個過程結束後，所有中國人都有拿到商品。
Output Format
對於每筆測資，請輸出$N+1$行，每行有一個非負整數。
第一行請輸出店家總共作廢了幾個商品。接下來$N$行請由最先到最後的順序輸出拿到商品的中國人編號。
Sample Input 1
6 9 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
3 1 5 1
3 6 2 1
Sample Output 1
3
1
2
5
6
4
Hints
本題共有五組測試資料。每組可有多個輸入檔案，全部答對該組才得分。
第一組27分，$T\leq 2, a_1\leq N<M\leq 10^ 4$
第二組22分，$T=1, a_1\leq N<M\leq 10^ 5$
第三組17分，$T\leq 3, a_1\leq N<M\leq 10^ 6$，不會有重組，且無論是進入隊列或發放商品都必定發生在隊伍的最前方或最後方
第四組34分，$T\leq 3, a_1\leq N<M\leq 2\times 10^ 6$
注意事項：
使用C++作答的同學，請在程式碼開頭加上#include<cstdio>，並利用scanf讀入資料、用printf輸出資料。使用cin / cout讀入/輸出資料可能會因為效率太差以致於程式執行時間超過限制。
scanf 常用的讀入方式如下：
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。
scanf("%u",&x); 讀入一個無號整數至unsigned int 型態變數x。
scanf("%llu",&y); 讀入一個無號整數至unsigned long long 型態變數y。
printf 常用的輸出方式如下：
printf("%d\n",x); 輸出一行包含一個int 型態變數x。
printf("%lld\n",y); 輸出一行包含一個long long 型態變數y。
printf("%u\n",x); 輸出一行包含一個unsigned int 型態變數x。
printf("%llu\n",y); 輸出一行包含一個unsigned long long 型態變數y。
Problem Source
Problem Set / Description by Yihda Yol
建國中學105學年度全國賽模擬賽pA
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~1 | 27 |
| 2 | 2~3 | 22 |
| 3 | 4~5 | 17 |
| 4 | 0~7 | 34 |