各種分治的套路彙總（分治）

咕咕咕。。。

NOIP退役預定？

最近膜你賽的分治題總是不會，窩太弱了qwq

基礎應用

快速幂？（某些多組詢問的矩陣乘法題，預處理出矩陣\(2^j\)的幂，然後每次取出合并，可以優化時間複雜度）

歸并排序？

翻轉排序？（NOIAC32 Sort）

序列分治

關于最值分治是序列分治中最常見的，要求的東西一般都長成這樣：\(\sum\limits_{l=1}^n\sum\limits_{r=l}^n F_{l,r}\)。

蒟蒻見過的又可以分為兩類：

• 将序列中點作為分治中心，考慮左邊最值對右邊的貢獻。如這道題。
• 将最值位置作為分治中心，考慮較小一側對較大一側的貢獻。例子就不友善舉出了。複雜度證明？可以把分治過程看成樹結構，套用樹剖/dsu on tree的方法來證明這也是帶一個\(\log\)的。

區間最值，區間與/或，區間\(\gcd\)/\(\text{lcm}\)等都有單調的性質，可能被瞎jb同時摻進某一道題裡。

線段樹分治

NOIP警告

CDQ分治

其實基本是闆子。

另外無重複元素三維偏序問題有更巧妙的容斥做法。