CDQ分治：

理解：用一個 \(\log\) 的代價去掉一個維度/一層分治可以代替一個數據結構。

應用：三維偏序：第一維排序，第二維分治，第三維數據結構。

細節：分治遍歷順序與數組何時排序 ？

一般三維偏序采取后序遍歷，這樣可以保證在劃分區間前后兩段的時候，是依據 cmp1 劃分的。下面演示一下其他遍歷順序（要多排序一下，跑得慢了）。

先序遍歷

中序遍歷

例題

P4169 [Violet] 天使玩偶/SJY擺棋子、

絕對值不好處理，考慮轉化為四個方向討論正負號來拆點絕對值。

動態加點的二維信息處理可以用在線二維數點類數據結構，比如 KDT，樹套樹。但是同樣可以離線，但是這個時候就需要添加一個維護：時間。進行三維偏序求最值，三維：時間序，\(x\) 軸，\(y\) 軸，

本題要進行四個方向的統計，重點注意本題四個象限分開處理后的寫法，以及對于第二維度的處理。由于是四個要分開統計所以要先記錄下來統計與修改操作用數組保存再進行第二維的排序。然后調用計算函數四次即可。

P4027 [NOI2007] 貨幣兌換

不要被題目形式所迷惑，股票題的最佳策略是 allin。

所以必然是一天投入所有錢，另一天賣掉所有持有股票。然后重復多次這個過程。設 \(f_i\) 表示第 \(i\) 天最多持有的錢數。其中

\(cnt_{a}=\dfrac{f_jR_j}{R_j\times A_j+B_j}，cnt_{b}=\dfrac{f_{j}}{R_{j}\times A_{j}+B_{j}}\) 表示某天最多可以得到的 \(A,B\) 股票個數。

可以李超線段樹優化，不過這里采用斜率優化。

因為式子中有 \(i\) 與 \(j\) 的乘積項，所以考慮斜率優化。

需要維護一個上凸殼，發現斜率和橫坐標均不單調怎么辦，可以用 \(CDQ\) 分治解決。第一維選取時間維度，第二維選擇橫坐標，第三維選取斜率。根據狀態轉移需要，選擇中序遍歷。由于加點希望按橫坐標，查詢希望按斜率，故 $ (l,mid) $ 按照橫坐標排序，$ (mid+1,r) $ 按照斜率排序。

P3769 [CH弱省胡策R2] TATT

本題是四維偏序可以采用 CDQ 套 CDQ。

第一次 CDQ 結束后根據分治中點打上標記，左邊為 \(0\)，右邊為 \(1\)。這樣就處理掉一維。然后就可以再來一個 CDQ 進行三維偏序。統計貢獻的時候只有標記為 \(0\) 的才能加入樹狀數組，只有標記為 \(1\) 的才可以進行答案累加。

注意由于狀態轉移需要，必須中序遍歷，同時不能忽視排序的穩定性，對第二維排序的時候仍然要以相同時第一維優先，對于三四維度排序同理。

整體二分

如果單個詢問可以用二分，而操作的貢獻是方便減掉的，那么對于多個詢問可以使用整體二分。其實就是多個問題一起二分，減少共同部分的計算。

P1527 [國家集訓隊] 矩陣乘法

這里二維區間 \(k\) 大，可以利用整體二分之后轉化為數點。

因為空間限制不大，所以這里的二維數點用二維樹狀數組來解決。

P4602 [CTSC2018] 混合果汁

注意這里的操作不具有可減性，于是整體二分過程中需要保留前面對后面的影響。

也就是數據結構內的一些信息在對于后續貢獻的時候不撤回。

P5163 WD與地圖

動態維護刪邊 SCC 內部 kth 信息。首先把刪邊變為加邊，動態維護加邊 SCC，線段樹合并維護 kth 信息。問題是我們還是不會維護加邊的 SCC 變化，這里可以很巧妙地利用整體二分，check 出每條邊最早什么時候能使得其左右兩端在同一個 SCC 中。最后離線根據這個時間來合并。

設每條邊最后的答案時間是 \(t_e\)。整體二分過程中，假設我們二分的是 \([l,r]\)，我們應該保證 \(t_e<l\) 的邊的影響已經保留（具體來說我們把 \(t_e<l\) 所連成的在同一個 SCC 內的點縮成一個點），這樣子每次做都可以保證單次 tarjan 的復雜度是 \(O(r-l)\)。注意這個縮成一個點的重標號只能對于遞歸到 \(\rm solve(mid+1,r)\) 的部分起效果，對于 \(\rm solve(l,mid)\) 的部分不能起效果，因為求的是左邊往右邊的貢獻，無法處理自己內部的貢獻。

總的時間復雜度 \(O(n\log n)\)。

P6684 [BalticOI 2020 Day1] 小丑

\(\rm Trick:\) 可以發現維護的信息具有交換律。于是禁用一個區間可以轉化為將序列復制一遍接在末尾，然后查詢 \([r+1,n+l-1]\) 之內的信息和。

發現對于一個左端點 \(i\) 滿足條件的最遠 \(R_i\) 具有單調性。于是考慮整體二分。

我們用 solve(l,r,tl,tr) 表示處理 \(R_l,R_{l+1}\dots R_r\)，且它們的值域在 \([tl,tr]\) 之間，可以通過維護并查集來快速判斷是否是二分圖。

線段樹分治

應用場景：支持動態修改的查詢類問題且用于查詢的數據結構難以快速刪除，或者詢問一段時間內（也就是說詢問一段時間內加入點的答案）的答案。

算法是在在時間-序列的二維矩形進行操作，正常按照時間一個一個做就是等價于對于時間進行掃描線，而我們可以離線利用線段樹維護時間軸。

我們將遇到的情況分成以下兩種。修改操作有生效時間（比如加點刪點），也就是說修改操作是帶撤銷的，單點詢問。還有一種就是單點修改，詢問一段時間區間內的答案。這兩種的本質都是對于詢問和修改其中一個是時間區間操作，一個是時間軸單點操作。對應一下時間軸單點操作就是時間線段樹的葉子節點，時間區間操作就是線段樹上分成 \(\log\) 個區間。

于是兩種問題的做法都是將區間操作的提前打到線段樹的節點上去，用一個 std::vector 保存，然后對于單點的操作，直接遍歷根到葉子節點，中途處理經過區間節點的操作。

具體來說對于第一種情況也就是修改操作是一段時間區間的，我們就把修改操作打到線段樹的每個節點上，對于一個葉子節點的詢問就是把從統計根到葉子節點上所有節點的答案再合并。因為根到葉子的所有節點代表的時間區間都是包含這個單點區間的。

對于第二種詢問一段時間區間的就是把詢問打到線段樹的節點上去，當經過該節點時進行詢問，然后對于修改操作，就是在根到葉子節點的所有節點上都進行該修改操作，因為根到葉子的所有區間都包含該修改時間點，都會被影響到。

關于實現方法，其實大部分時候我們并不需要建立真正的線段樹，只是用到了該結構而已。如果處理每次修改操作？

根據我們處理的信息是否具有可并性，將方式分為兩種。

當然這里不討論第二種類型的查詢，因為你查詢一段時間范圍的詢問，將詢問拆開的過程本身就必須保證其具有可并性，否則第一步就不滿足了，于是遇到這種類型的我們下文講的兩種方式都適用。

討論第一種類型，就是在某個時間點提出詢問，當信息具有可并性的時候，我們采用本質為樹套樹的做法，外層的樹是對時間軸建立線段樹，內層的樹是一些數據結構，對于每個節點新建一個數據結構，將涉及的操作都放進去，然后對于子樹內的葉子節點上的詢問（對應第一種類型）或者該節點上的詢問（對應第二種類型）進行查詢，最后一個葉子節點的答案就是根到葉子的路徑答案并。

當信息不具有可并性的時候（比如圖的聯通性），我們就不能拆開到每個祖先節點上進行詢問了，只能 dfs 到葉子的時候再詢問了。這個時候在離開這個節點的時候需要用到數據結構的回退，于是必須滿足數據結構的可回退性，所以用到的數據結構必須支持回退，比如要是用并查集的話就只能啟發式合并了，不能路徑壓縮。

P5787 二分圖 /【模板】線段樹分治

首先是經典擴展域并查集判定二分圖，然后套一層線段樹分治來支持邊的出現一段時間。

P5631 最小mex生成樹

先考慮暴力枚舉答案 \(x\)，將所有權值為 \(x\) 的邊刪去，查看連通性。

但是發現每次只修改一部分邊，其他大部分邊都是不變的卻每次都要枚舉到，可以不可以合并重復操作呢。這就啟發我們用 \(\rm solve(l,r)\) 表示邊權為 \([l,r]\) 之內的邊都不加入。這樣在處理 \([l,r]\) 中的邊的時候就可以不重復處理 \([0,l-1] \cup [r+1,V+1]\) 中的邊了。每次先把右邊的邊全部加入，然后處理左半邊，再撤回，加入左半邊的邊，處理右半邊，再撤回。最后在葉子節點處查詢即可。

同時注意細節，本題求的是 \(\rm mex\)，所以邊權需要從 \([0,\max w+1]\) 都要考慮。

P5443 [APIO2019] 橋梁

操作的時間順序，使得我們想到線段樹分治算法。但是可持久化并查集或者克魯斯卡爾重構樹不具有回退性，所以用不了線段樹分治，但是可以用 \(KDT\) 分治，其中一維是可持久化。現在還沒太掌握，以后再更。

下面介紹遇到不可回退數據結構的處理方法，根號重構，也叫操作分塊。

考慮兩種算法，一個是直接修改，暴力查詢連通性。我們會感覺到每次圖的聯通性每次的反復查詢似乎有些重復，本著減少重復計算的原則，可以通過對查詢邊權升序排序，然后按照邊權升序大小依次加入這樣只需要維護一個并查集即可。對于沒有修改的邊，可以直接一邊查一邊加入，而對于有修改的邊則需要每次查詢都修改一遍。發現此時修改操作又重復了，如何平衡查詢次數與修改次數之間的關系呢，我們可以分塊！快外保存修改，塊內維護一個并查集每次重新修改。

P4585 [FJOI2015] 火星商店問題

這道題就上面說的第二種類型的線段樹分治，我們需要查詢一段時間內的答案。

本題有時間和區間兩個維度同時要求最大異或值。

解法一：最直接的想法就是線段樹套字典樹，先用線段樹解決區間問題，再用字典樹解決最大異或值，時間問題直接在字典樹節點上打標記即可。

解法二：線段樹分治+可持久化字典樹。用線段樹分治處理時間序，用可持久化字典樹完成區間異或最大值。

其實綜合解法一二會有一個疑惑就是為什么不能可持久化字典樹加時間標記呢？原因是用可持久化處理區間信息一般要有可減性（畢竟是 \(val_r-val_{l-1}\) 湊出來的區間嘛），而時間標記不具備可減性！

QOJ8074. Multiply Then Plus

令 \(y=a_i\times x+b_i\)，那么 \(b_i=(-x)\times a_i+y\)。

如果沒有修改，對于不同 \(x\) 全局查詢。那么就是維護一個在 \(b_i-a_i\) 的坐標系中維護一個上凸殼。每次對于斜率 \(-x\) 進行二分即可。如果改為先對 \(-x\) 排序，再離線查詢可以去掉二分改用指針維護做到線性。

如果是區間的話，可以用線段樹維護凸包，每次將詢問分裂為 \(\log\) 個詢問取最大值。同理如果每次二分的話，是 \(O(n\log^2n)\) 的。但是我們還是可以對于 \(-x\) 排序，然后對于線段樹每個節點維護一個指針，表示上次掃描到哪里了，每次移動指針就行了。可以做到 \(O(n\log n)\)。

本題有了修改操作可以進行線段樹分治。可以發現本題是對于單一時間點詢問，但是修改操作有生效時間。于是我們將每個詢問都打到對應時間點的葉子節點到根的每個點上，然后將修改操作拆分成 \(\log\) 個放到對應節點上，每到一個節點就建立一顆線段樹然后處理對應詢問即可。時間復雜度 \(O(n\log^2 n)\)。

QOJ8703.天氣預測

想不到吧，這也可以線段樹分治，如果去思考動態 dp 的話就墜機了。

考慮從兒子向父親合并是一個 NTT 分治或者 多項式 ln \(+\) exp 的形式，不好動態去做。

使用線段樹分治維護時間軸，每個點開一個動態開點線段樹，維護該時間區間內為 \(1\) 的概率，注意沒有 pushup，因為只有葉子節點處的概率值才有意義。

在樹上向上轉移就代表線段樹合并的過程，這里由于兒子之間是相互作用的，所以我們應該用多個線段樹同時合并。

鴿鴿鴿，抱歉退役之前來不及補了，大學有時間再完善這題題解。

啟發式分裂

序列分治，面對不均勻分裂的時候，必定有大有小，我們掃描短的一側即可！

當然處理樹上聯通塊分裂信息也可以使用類似思想。

P4755 Beautiful Pair

分治處理區間 \((l,r)\) 發現肯定是區間中的點跨過最大值點對區間另一邊的點產生貢獻。

然后在以最大值點為劃分分別計算兩邊答案。但是題目極端數據可能讓最大值點的分布不均勻，導致時間復雜度退化。

于是我們可以在每次選擇最大值點后，掃描較段的一邊，較長的有一邊用數據結構查詢。此時可以在線主席樹，也可以離線樹狀數組。這樣子復雜度就正確了。

XYD4290.笛鐳特

給定一棵點權互不相等的樹，每次操作對于所有聯通塊刪除當前聯通塊的最大值/最小值的點，不斷分裂聯通塊。問多久能刪完這棵樹，其中奇數輪刪最小點，偶數輪刪最大點。

可以用線段樹維護 dfs 序來快速查詢一些子樹極值信息。我們改變處理順序，用 \(\rm solve(u,dep)\) 表示當前處理 \(u\) 子樹且操作論數為 \(dep\)。每次找到該子樹內未被刪除的極值點 \(v\)，刪除其在線段樹上的信息，枚舉 \(v\) 的所有兒子 \(s\)，\(\rm solve(s,dep+1)\)。最后回來再 \(\rm solve(u,dep+1)\)，直到所有點都被刪光。很巧妙吧，因為所有聯通塊是獨立的，所以我們可以改變其操作順序。

概括來說就是每次找到最值之后先對其所有子樹處理，而不是同時對于所有分裂出來的聯通塊處理，處理完一個點后立刻刪除其在線段樹上的信息，時間復雜度 \(O(n\log n)\)。

還有一種更加普適的方法，之前沒見過這個 Trick，就稱之為樹上啟發式分裂吧。

這種樹上聯通塊行走的問題肯定要聯系到重心上，這樣子才能保證復雜度。

本題由于不是直接跳到重心，所以有點難辦。但我們可以對于信息的利用聯系到重心上。具體來說我們用 \(\mathrm{solve(u,0/1)}\) 表示處理 \(u\) 的一個聯通塊，而 \(0/1\) 表示我們是否需要進行遍歷處理。初始肯定是要傳入 \(1\) 的也就是要預處理，我們算出重心，然后將所有點的信息加入堆中，找到極值點 \(c\)，\(u\gets c\)。我們現在刪點 \(u\) 點，那就需要處理 \(u\) 的所有相連點下方的聯通塊。對于所有非重心子樹 \(\mathrm{subtree(v)}\)，我們進行 \(\mathrm{solve(v,1)}\)，并且刪點這些子樹在堆中的信息。對于重心所在子樹，\(\mathrm{solve(v,0)}\)，因為我們已經在堆中保存了 \(v\) 子樹的信息，不需要重復處理了。但是需要注意由于我們不能遍歷該子樹，所以新重心不能直接求出，這里很巧妙，直接設老重心為新重心，可以發現需要新處理的子樹大小還是 \(\le \dfrac{sz_u}{2}\) 的，只不過這是上一輪的 \(u\)，但復雜度還是對的。最后一個細節就是我們可以維護一個 \(to_u\)，表示 \(u\) 點往哪個相鄰點走可以走到重心，來得到重心和 \(u\) 點相對位置關系。

分治的其他應用

P1429 平面最近點對

根據 \(x\) 坐標排序之后分治，重點是如何求出跨越分治中心的貢獻。

設左右兩側遞歸過來的最小值是 \(d\)，將所有和 \(mid\) 的橫坐標距離 \(\le d\) 的點都加入點集之中，對于點集進行縱坐標排序，枚舉點集中的每一個點，再枚舉所有和它縱坐標不超過 \(d\) 的點集中的點，更新答案。首先這兩步剪枝都是顯然不影響最優化結果的，同時可以證明最后的枚舉對于點集中的每個點只會枚舉到 \(\le 5\) 個點，所以這是正確的。

P8868 [NOIP2022] 比賽

這里僅介紹 \(52 \rm pts\) 的分治解法，作為最值分治的一種思路。

對于單序列，建立笛卡爾樹，然后啟發式分裂是很經典的 trick，但是對于雙序列，最值點不重合，我們該如何處理？做法是正常進行分治，每次從中點進行分治，然后維護 \(mid+1\to r\) 的前綴極值，和 \(mid\to l\) 的后綴極值。

接下來我們枚舉 \(2\times 2\) 最值分布位置，然后進行雙指針。比如欽定兩個最值都在左邊，就拿左邊兩個后綴極值與右邊的前綴極值比較，都成功，才能繼續推進，累加貢獻。

P8227 「Wdoi-5」建立與摧毀的結界

鴿