百年後的未來,某些狂熱科學家創造了人造生物"Elcatnet",中譯"手觸"。 雖然手觸原本是寄生動物,但因為手觸繁殖力強加上他們的突變機制與原來的生 物不同,他們是靠自己的意志產生突變的!
很快地,出現了會光合作用的手觸、會獵捕其他生物的手觸、會分解動植物遺骸 的手觸。特別的是,手觸會把卵生在其他物種體內,吸取宿主的養分。
五年後,有一隻手觸從實驗室逃出。三十年內,手觸造成世界各地嚴重得生態問 題。一百年內,手觸把地球上 70%的物種消滅。 人類因為懼怕這些手觸,而移民到了其他星球。慶幸的是,根據人類研究發現手 觸沒有求知慾,所以不必擔心他們會發明太空梭。不過事情似乎沒有這麼簡單。
把時間往回推,此時是手觸才被創造不久,各個領域的科學家都爭相研究手觸。
然而身為建國中學的你也不例外,你正在實驗室作實驗。你知道:
1.手觸們只會進行兩種互動,不是攻擊就是交配。
2.你研究的手觸只有兩種,一種是 s 觸,另一種是 m 觸。同族間只會交配,異族 間只會攻擊。
3.有些 s 觸會因為 m 傾向變大而突變成 m 觸;有些 m 觸會因為 s 傾向變大而突 變成 s 觸。
4.因為你無法同時觀察所有手觸,所以當你發現有隻手觸你疏忽了,你會暫時把他歸為未知,因為他可能在你疏忽的這段期間突變數次,但你可藉由之後的紀錄 重新得知他是哪一種手觸。
有時候你會因為被手觸攻擊而記錄錯所以你必須寫一個程式來檢查。 如果一個紀錄與你當下紀錄產生矛盾那他會被刪除。
輸入第一行含兩個正整數 n,q 代表手觸數量跟記錄數量。
每組紀錄第一個數字是一整數 c :
如果 c 是 0 或 1 後面會有兩個正整數 a,b
0 代表他們在交配,1 代表他們在 Battle。
如果 c 是 2 或 3 後面會有一個正整數 k
2 代表手觸 k 突變成另一種了,3 代表你疏忽了手觸 k。
對於100%測資,n,q≤2,000,000; 0≤c≤3; 1≤a,b,k≤n(保證 a 不等於 b)
輸出一個整數代表總共有幾筆資料被刪除了
對 Sample Input 1
第三筆記錄是錯的因為他與第一筆和第二筆記錄矛盾
第五筆記錄是沒錯因為 3 號手觸突變了
對 Sample Input 2
第四筆記錄是錯的因為他與第一筆和第二筆記錄矛盾
第五筆和第六筆記錄是沒錯因為你疏忽了 2 號手觸
第八筆記錄是錯的因為他與第六筆和第七筆記錄矛盾
原TIOJ1783 / problem setter: fenzhang
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 10 |
2 | 1 | 10 |
3 | 2 | 10 |
4 | 3 | 10 |
5 | 4 | 10 |
6 | 5 | 10 |
7 | 6 | 10 |
8 | 7 | 10 |
9 | 8 | 10 |
10 | 9 | 10 |