HOJ 226: CP (中)

題目在這裡,HOJ 226

有關的題目出現於NPSC 2014 高中組決賽pD。

前置要求:treap (split, merge)跟在上面實作區段操作(請參考資訊枝幹)。

這裡沒有完整的解答code,因為AC是要用血汗換來的才值得 :-)

Treap

我討厭單字母l的變數名稱(跟1太像了。我沒有被這個雷過,這只是自己對自己程式碼可讀性的要求),所以我的子樹叫做lc(left child),rc(right child)。

struct Treap {
    Treap * lc;
    Treap * rc;
    unsigned pri;
    char val;
    int size;
};

int size(Treap * a) { return a ? a->size : 0; }
void pull(Treap * a) {
    if (a) a->size = 1 + size(a->lc) + size(a->rc);
}

持久化/Copy-On-Write

一般來說

純粹只想關treap的話可以跳掉這段。

Copy-on-write就是你操作一個資料結構的時候,保留舊的東西不要刪掉或改掉。

舉簡單的linked list當例子:假設你有一個list

x = [1,2,3,4,5,6,7,8,9,10]

你想要插入一個42得到

y = [1,2,42,3,4,5,6,7,8,9,10]

但是不想改掉x,又不想做一個完全新的list,因為畫的時間跟記憶體可能太多了。 如果用singly-linked list的話,可以用指標讓xy[3,4,5,6,7,8,9,10]這一段共用,不需要把[3,4,5,6,7,8,9,10]存兩遍:

x = (1)→(2)→(3)→(4)→(5)→(6)→(7)→(8)→(9)→(10)
             ↑
y = (1)→(2)→(42)

這樣本來要做11個新的節點來表示y,現在只要3個。不過這樣做的前提就是,你不可以之後偷偷改掉x後面的節點存些什麼,如果這樣做就必須承受y也被改掉的結果。

用到treap上面

以前在merge裡面寫

a->rc = merge(a->rc, b);
pull(a);
return a;

現在要假設別的地方可能會用a代表同一個區段,為了不改到那些別的地方,我們不能修改a,所以只好回傳新的Treap,把它的子節點換掉。

Treap * aa = new Treap();
aa->lc = a->lc;
aa->rc = merge(a->rc, b);
aa->pri = a->pri;
aa->val = a->val;
pull(aa);
return aa;

所有會改掉現存的Treap改成類似的做法之後,好處是在任何時候,你如果把一個節點做完,那它跟它下面所有的東西就永遠代表同一段資料(除非你電腦壞掉)。 所以一個節點可以用在兩個或更多的地方來表示同一段資料,把之後在一邊操作它不會影響到它在別的地方代表什麼,因為操作改的節點都是剛剛新做的節點。

這樣,你就可以放心的把一個Treap重複merge到不同的地方了。 例如,你可以merge(m, m)把一個區段複製成兩倍,但記憶體不會用到兩倍。

引用計數

(NPSC那一題不需要這一項優化。)

使用Copy-On-Write會製造很多垃圾,而且在這一題裡還有多於106的字母可以刪掉,不處理的話會Memory Limit Exceed。所以沒有用的Treap必須刪掉。

什麼時候會產生沒有用的Treap呢?split跟merge跟外面實作操作的時候,本來舊treap會被摧毀,修改而成新的,被回傳的treap。現在因為持久化不能直接刪掉舊的,不過會少引用它所以「可能」可以刪掉。問題就是如何知道這個「可能」什麼時候成立。

我是苦苦的手刻引用計數才過的:記錄每一個treap有幾個指標指向它,如果到0就把treap delete掉。

我本來以為可以用STL的shared_ptr,不過聽說有人寫了發現太慢了。我不知道有沒有更好的做法。

基本上,引用計數就是加入一個欄位:

int refs;

之後在適當的地方呼叫:

void takeRef(Treap * t) {
    if (t) t->refs++;
}
void dropRef(Treap * t) {
    if (t) {
        t->refs--;
        if (t->refs <= 0) {
            dropRef(t->lc);
            dropRef(t->rc);
            delete t;
        }
    }
}

適當的地方並不明顯。這邊要debug很久很久很久(至少如果你是我的話)。

Randomized Binary (Search) Tree

但這題跟NPSC那題直接用最普通的treap都有一個問題,就是複製區間的時候如果連priority一起複製就會失去讓treap保持指數深度的隨機性質。但你又沒辦法隨機生出一個在樹堆裡有一樣「大小含義」的priority。不能用跟生新的節點時一樣的隨機,因為大的Treap要通常比小的Treap的priority大。(或者比較小,看你heap性質選擇哪個方向。)

似乎最好的解決方式是改用treap的近親randomized binary (search) tree:節點上只記錄size(=節點跟節點所有子孫總數,反正Treap的區段操作本來就要用),每次合併size a跟size b的樹時,呼叫一次隨機數生成器,以a/(a+b)的機率把size a樹的根當新的根,以b/(a+b)的機率把size b樹的根當新的根。

機率很重要

模擬兩邊當根的機率a/(a+b)跟b/(a+b)是必須的,不能純粹用1/2的機率,才可以有好的深度性質。

可以想一下,這跟本來的Treap裡都有好性質,就是你如果併起了n個隨機的節點,那麼每個節點當根的機率都是一樣的1/n,然後下面的節點分成兩塊,遞迴下去。這樣就可以救回O(log n)深度性質,只是呼叫隨機數產生器的時候不一樣,如果你要用很高級,很耗時的隨機數產生器,可能就會有差,不過這裡不用煩惱這種東西。

不能直接用大的那一邊當根嗎?

你可能會想說,與其隨機選根,不如就永遠選機率比較大的那一邊?想像一下,如果你有一個空的Treap,然後一直把一個頂點的Treap從右邊併進去。它會退化成往右下長的一直線。還是要有機率把大的子樹踢到一邊。

隨機是一件很神奇的東西。

奇怪的另解

其實我第一次AC這一題的時候還沒放棄Treap,而是複製了一個Treap就用奇怪的方式幫它隨機產生一個priority。(這樣連heap性質都不保,真恐怖。不過不會影響正確性。)

int randomPriority(int size) {
    rseed = 0xdefaced * rseed + 1;
    unsigned int q = 0xffffffffu / (unsigned int) size;
    return r % q;
}

這樣的速度顯著的比較慢(55626ms vs 32490ms),不過AC就是AC吧!我沒有試著用數學角度研究這樣的Treap複雜度如何。(注意這樣是假設merge的時候,priority較小的子樹當根。)