This post was written in Traditional Mandarin Chinese for my fellow competitive programmers in Taiwan.
有關的題目出現於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的話，可以用指標讓x跟y的[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代表同一個區段，為了不改到那些別的地方，我們不能修改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，不過聽說有人寫了發現太慢了。我不知道有沒有更好的做法。
基本上，引用計數就是加入一個欄位：
之後在適當的地方呼叫：
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較小的子樹當根。）