TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

22.7% (5/22)

Tags

Description

百年後的未來,某些狂熱科學家創造了人造生物"Elcatnet",中譯"手觸"。 雖然手觸原本是寄生動物,但因為手觸繁殖力強加上他們的突變機制與原來的生 物不同,他們是靠自己的意志產生突變的!

很快地,出現了會光合作用的手觸、會獵捕其他生物的手觸、會分解動植物遺骸 的手觸。特別的是,手觸會把卵生在其他物種體內,吸取宿主的養分。

五年後,有一隻手觸從實驗室逃出。三十年內,手觸造成世界各地嚴重得生態問 題。一百年內,手觸把地球上 70%的物種消滅。 人類因為懼怕這些手觸,而移民到了其他星球。慶幸的是,根據人類研究發現手 觸沒有求知慾,所以不必擔心他們會發明太空梭。不過事情似乎沒有這麼簡單。

把時間往回推,此時是手觸才被創造不久,各個領域的科學家都爭相研究手觸。

然而身為建國中學的你也不例外,你正在實驗室作實驗。你知道:
1.手觸們只會進行兩種互動,不是攻擊就是交配。
2.你研究的手觸只有兩種,一種是 s 觸,另一種是 m 觸。同族間只會交配,異族 間只會攻擊。
3.有些 s 觸會因為 m 傾向變大而突變成 m 觸;有些 m 觸會因為 s 傾向變大而突 變成 s 觸。
4.因為你無法同時觀察所有手觸,所以當你發現有隻手觸你疏忽了,你會暫時把他歸為未知,因為他可能在你疏忽的這段期間突變數次,但你可藉由之後的紀錄 重新得知他是哪一種手觸。

有時候你會因為被手觸攻擊而記錄錯所以你必須寫一個程式來檢查。 如果一個紀錄與你當下紀錄產生矛盾那他會被刪除。

Input Format

輸入第一行含兩個正整數 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)

Output Format

輸出一個整數代表總共有幾筆資料被刪除了

Sample Input 1

2000000 8
0 1 2
0 2 3
1 1 3
2 3
1 1 3
3 5
2 5
3 6

Sample Output 1

1

Sample Input 2

2000000 8
0 1 2
0 2 3
3 2
1 1 3
1 1 2
1 2 3
1 3 25
1 2 25

Sample Output 2

2

Hints

對 Sample Input 1
第三筆記錄是錯的因為他與第一筆和第二筆記錄矛盾
第五筆記錄是沒錯因為 3 號手觸突變了
對 Sample Input 2
第四筆記錄是錯的因為他與第一筆和第二筆記錄矛盾
第五筆和第六筆記錄是沒錯因為你疏忽了 2 號手觸
第八筆記錄是錯的因為他與第六筆和第七筆記錄矛盾

Problem Source

原TIOJ1783 / problem setter: fenzhang

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10