PKU 數據結構習作

今天無聊，做起CSC3270四道數據結構習作。


PKU1182 食物链
依據路徑壓縮，可以對x-->y帶三種標號﹕ label(x) = 0 (x 與 y 同類), 1 (x 吃 y), 2 (y 吃 x)。
計算路徑計縮時必須先取x的根點, rx。 對於find(x)一遍後，最多只有這種結構﹕x-->y-->rx。假設它是合法的，那麼label(x)的更新必然是(label(x) + label(y))%3 (可用簡單向量理解)，然後對x進行路徑壓縮。
要判斷x y的關係，先尋找它們的根rx及ry。如果rx == ry，可以直接判同類(label(x) = label(y))或者x吃y ((label(x) - label(y) + 3) % 3 == 1 及 x != y)。
若rx != ry 顯然不會有矛盾。這意味著可以通過并合兩者來構造新的樹。對於x-->rx-->ry<--y，若果認為x跟y是同類的話，必有label(x) + label(rx) = 0 + label(y)。若果認為x吃y的話則有label(x) + label(rx) = 1 + label(y)。繼乎直接更新label和進行普通union就成。

PKU2481 Cows
如果任何可以強於[Si, Ei]的牛[Sj, Ej]，必須有Sj <= Si和 Ei <= Ej。可以想到當我們從最大的E值開始，相同E值的依最小S值來處理線段的話，保証處理當前線段時，所有強於它的線段都已經處理過了(並且不強於它的線段沒有被處理過)。此刻強於線段i的已處理線段必然都有<=Si的值。因此我們可以憑已處理並少於等於Si的S值進行統計並計算答案。然後把Si加進表中。這裡我們直接使用樹狀數組。對於重覆的[S, E]值，我們直接用上一個處理線段的值，因兩者有相等答案。緊記亦需把它加進數組中。

PKU2777 Count Color
純粹普通線段樹應用。一種顏色可用一個位元來記著。

PKU1442 Black Box
用最大堆及最小堆。每次把新的數放進最大堆。只要當前最大堆的大小超過counter，便把它放到最小堆內。最大堆永遠保持首counter小的數。最小堆的最小值便是答案，記得把它放會最大堆中。