OI中一些常見實用的套路【更新中】

資料結構

• 在維護樹上路徑時，如果隻是點的獨立的加減，可以考慮用括号序來維護（拆成兩部分）
• 需要求樹上很多路徑中k近/距離和 一類，考慮點分治/在點分樹上解決。
• 子樹求和可以轉化為DFS序上區間求和
• 樹狀數組可以區間查詢/修改（差分）
• 需要查詢序列上區間資料結構，隻要滿足總和是可以接受的範圍，可以用線段樹，每個區間維護一個這樣的資料結構（例如AC自動機等）
• 多元偏序問題，排序可以降維，CDQ分治可以降維，剩下隻需要樹狀數組/線段樹
• 樹上連通塊有機率出現，再加上和的次方，往往可以拆開來，變成任意選K個可重，有序的點，考慮貢獻。

• 當又需要分塊，每個塊維護資料結構時，塊的大小考慮調整（不再一定是 n \sqrt n n

  ​）（平衡規劃）

• 同理，對于圖論中度數總和固定、多組詢問查詢的點數固定，查詢點需要枚舉出邊，但可能一直查詢度數比較大的點。此時考慮平衡規劃。（詢問點個數/度數 大于/小于 n \sqrt n n

  ​分開來做）

• 對于點分治時兩個不同的子樹的結果混在一起需要判掉，可以考慮幾種辦法：
  • 在點分樹上兒子記錄目前點分樹子樹中的節點到父親的結果，計算父親時在這裡減去。
  • 維護DFS序，兩個子樹對應兩個無交的區間，可以考慮區間分裂一類的做法。
• 對于有很多顔色的點，需要對相同顔色計算影響，可以把每個顔色拉出來在DFS序上搞事情（相鄰+1，lca-1一類）
• 如果又加上了深度限制，那麼相當于除了DFS序這一維，還多出了深度這一維，可以考慮（主席樹/CDQ分治/二維資料結構），也可以将點排序以後用線段樹維護DFS序。
• 對于這樣一類問題：每個元素（邊/點之類）具有權值/權值範圍，每次隻需要考慮權值是一定值/一定範圍的元素的影響，可以考慮建立權值線段樹，将元素的影響挂線上段樹對應的所有區間上，查詢就查詢區間。
• 當需要查詢樹上是否存在一條路徑過兩個點時，可以将路徑端點記在DFS序上，然後兩點子樹查詢，這就變成了兩個區間數點的問題（二維偏序/掃描線/DFS動态樹狀數組維護增量）
• 需要維護序列輪轉問題時，不一定非要splay，如果輪轉很特殊時可以采用線段樹+預留白位的形式轉化為單點修改。
• 想要存儲很多東西的0/1狀态，且需要支援xor/or/and等操作時，bitset是個非常好的選擇（計算複雜度可以除以32），别忘了bitset還有左移右移操作，可以用來處理+或-
• 替罪羊樹跑的很快。
• 帶旋轉的平衡樹是很難在内層套上線段樹的，是以平衡樹套線段樹應考慮替罪羊樹或無旋treap
• 一堆操作+詢問的題，如果很容易處理一堆操作對一堆詢問的貢獻，可以考慮分治，你可以考慮權值/時間分治
• 一棵Trie如果要維護+1異或，那麼不妨從低位到高位建Trie
• 線段樹分治往往應用在一些對象知道插入和删除時間時，維護合法情況很容易，但撤銷非法情況比較困難時。
• 要算一個點和一堆點的距離的時候，可以考慮将距離拆成兩點深度和-2*lca深度，lca深度可以表示成lca到根的節點數，那麼直接樹鍊剖分鍊上區間加區間求和即可。
• 要做一堆數的lcm的時候，可以考慮每個質因子的指數最大值，然後将每一個 p 1 , p 2 . . . , p k p^1,p^2...,p^k p1,p2...,pk都看做一種顔色，每種顔色的權值為p，然後相當于是求每種出現過的權值的積。
• 對路徑邊權最大值有限制，可以考慮克魯斯卡爾重構樹。
• 矩形加，單點求值，可以考慮拆貢獻帶修主席樹字首和，也可以直接KD樹（線段樹+splay顯然很蠢）

圖論

• 求點雙連通分量棧中仍然可以存點，圓方樹維護起來很友善。
• 無向圖中最大值最小的路徑一定在最小生成樹上
• 合并兩個連通塊的直徑，直接比較四個端點兩兩連起來的長度即可。
• 一些有代價的完美覆寫問題，選格子有行列限制有代價/收益的題往往考慮網絡流。
• 看到資料範圍隻有幾十或者幾百，然後諸多限制，要最優化一些東西，也可以考慮網絡流。

多項式

• 碰到諸如 ∏ i = 1 n ( 1 + p i x ) ， ∏ i = 1 n ( 1 + i x ) ， ∏ i = 1 n ( i + x ) \prod\limits_{i=1}^{n}(1+p^ix)，\prod\limits_{i=1}^{n}(1+ix)，\prod\limits_{i=1}^{n}(i+x) i=1∏n​(1+pix)，i=1∏n​(1+ix)，i=1∏n​(i+x)的時候，先不急着分治NTT，它可以倍增在一個log的複雜度求出。

計算幾何

• 要處理出一個平面圖的所有區域時，有一個很友善的做法：将所有點的連邊按極角排序，每條邊的兩邊各建一個點，枚舉每個點的所有連邊，相鄰的邊夾着的區域對應的兩個點用并查集連起來，這樣得到連通塊，每個連通塊就是一個區域了。

其他

• 如果遇到 n 3 n^3 n3的轉移矩陣，但是我們一次隻想知道的結果是一維的（即暴力乘的複雜度是 n 2 n^2 n2），那麼可以考慮倍增預處理轉移矩陣的幂，求出轉移矩陣 2 0 , 2 1 , 2 2 . . . 2^0,2^1,2^2... 20,21,22...次的結果。詢問的時候隻需要 n 2 log ⁡ n^2\log n2log而不是 n 3 log ⁡ n^3\log n3log，預處理則是 n 3 log ⁡ n^3\log n3log，總的複雜度就可以變成 q ∗ n 2 log ⁡ + n 3 log ⁡ q*n^2\log+n^3\log q∗n2log+n3log
• DP時，如果狀态很大，結果很小，可以考慮能否将結果與狀态互換。
• 涉及網格圖帶權，行列選擇限制/覆寫一類的問題，可以考慮網絡流。
• 一個經典問題：有一個序列，給出若幹個區間，問有多少種選法使得選出的區間能覆寫整個序列。 我們考慮容斥，顯然容斥系數是(-1)^強制不覆寫的位置個數，記f[i]為前i個位置都已經确定了,第i個位置不選的方案數和，它可以從 f [ j ] ∗ ( − 1 ) ∗ 2 k f[j]*(-1)* 2^k f[j]∗(−1)∗2k轉移而來，我們把所有區間挂在右端點，從左到右掃的時候做區間乘法即可。
• 一個小數如果結果很多位，算乘積之類得到，可以考慮用對數