tony0530 的小窩

摘要： 可并堆 可并堆有三種常見方法：斜堆，左偏樹，隨機(jī)堆我們分別聊聊這三種堆吧！ 斜堆 斜堆的構(gòu)建其實(shí)是和二叉堆差不多的，它只是用鏈表來(lái)維護(hù)關(guān)系罷了，這是構(gòu)建代碼: struct Heap { Heap *lson, *rson; int val; Heap(int n = 0) { val = n; l 閱讀全文

摘要： 首先，請(qǐng)注意 \(Slope Trick\) 可不是斜率優(yōu)化，是一種通過(guò)維護(hù)斜率序列的優(yōu)化，它是有一定范圍限制的： 連續(xù)。 是分段一次函數(shù)。 是凸函數(shù)。 每一段的斜率較小（通常為 \(O(n)\)），且均為整數(shù)。 我們發(fā)現(xiàn)如果此上類型的函數(shù)相加之后還是上面的一種函數(shù)。 它通常用來(lái)維護(hù) \(DP\)， 閱讀全文

摘要： 樹套樹 概念 顧名思義，一個(gè)樹套著另一個(gè)樹(bushi) eg. 維護(hù)一個(gè)線段樹，并且對(duì)于每一個(gè)節(jié)用平衡樹進(jìn)行維護(hù) 樹套樹有很多種，外層的樹可能有很多種，常見的是線段樹與樹狀數(shù)組，內(nèi)層的樹最常見的是平衡樹，也有可能是其他的 T1 : 樹套樹-簡(jiǎn)單版 -> 是線段樹套 \(STL\) T2:樹套樹 - 閱讀全文

摘要： LCT學(xué)習(xí)筆記 和樹鏈剖分比較相似，但是它的時(shí)間復(fù)雜度是 \(O(nlogn)\), 樹鏈剖分是 \(O(nlogn^2)\) 維護(hù)一個(gè)森林，可以支持以下操作 求聯(lián)通兩點(diǎn) \(x\), \(y\) 的路徑上的所有點(diǎn)的某一求值(eg.\(xor\)) 將不聯(lián)通的 \(x\), \(y\) 之間增加一條 閱讀全文