1.
一眼，區(qū)間肯定到結(jié)尾
然后從后面掃，隨便統(tǒng)計一下個數(shù)即可
2.
剛看很難
再看詐騙
發(fā)現(xiàn)限制是要求同等深度，然后最小的必須有兩個
然后這個是個獨(dú)立問題，一看就很簡單
3.
烤柿沒調(diào)出來，改一個地方就過了
服了，如此實(shí)力，如何 NOIP ?
發(fā)現(xiàn)每個位置維護(hù) \(f[i]\) 表示 \(i\) 開頭最短的合法右端點(diǎn)
發(fā)現(xiàn)這個單調(diào)
用線段樹二分
然后這個求答案分兩部分，轉(zhuǎn)移直接區(qū)間覆蓋
4.
暴力是用并查集暴力兩兩合并
肯定要優(yōu)化建邊條數(shù)
我考慮分塊，對每個數(shù)往后分 \(\sqrt{n}\) ，最后連邊整塊的
這樣對整塊再用一個并查集就行了
復(fù)雜度 \(n \sqrt{n}\)
正解是用倍增 + ST 表
類似的，開 \(\log\) 個并查集表示以 \(i\) 開頭不同 2 的冪次長度
然后發(fā)現(xiàn)這個東西可以下傳
就是一個大的區(qū)間對應(yīng)相等，可以看做左右兩個小區(qū)間分別相等
然后從大到小下傳即可
5.
發(fā)現(xiàn)是樹上到根路徑的斜優(yōu)
這里有 3 種解決方法
一種是直接維護(hù)可插銷凸包，就是二分彈掉多少，直接將頭指針記錄，撤銷時直接改回去就行，每次只會改一個元素，維護(hù)區(qū)間，加一個樹狀數(shù)組即可
時間 \(n \log^2 n\)
一種是維護(hù)李超線段樹，李超線段樹好撤銷，直接用線段樹套上，加樹剖就行了
不加樹剖撤銷空間是 \(log^2\) 的
時間 \(n \log^2 n\)
最后一種利用出棧序，也就是每個結(jié)點(diǎn)離開 \(dfs\) 的順序。直接在點(diǎn) \(i\) 及其最遠(yuǎn)的滿足 \(d_i??d_j?≤l_i\)? 的祖先 \(j\) 的出棧序?qū)?yīng)的區(qū)間上查詢。容易發(fā)現(xiàn)區(qū)間內(nèi)不在 \(i\) 和 \(j\) 的路徑上的點(diǎn)都未被訪問到，不會對答案產(chǎn)生貢獻(xiàn)。這樣就不需要樹鏈剖分了。時間復(fù)雜度 \(O(n\log^2n)\)，空間復(fù)雜度 \(O(n\log n)\)。
6.
P9266 [PA 2022] Nawiasowe podzia?y
SH_A 講的丐版 決策單調(diào)性 ，qk 講的這道題
預(yù)處理括號，給 (--)(--)(--) 這種括號染色，每次加右括號，相當(dāng)于數(shù)同顏色左括號個數(shù)
直接套用丐版 決策單調(diào)性，用類似莫隊的指針移動
7.
決策單調(diào)性板子
要用 long double ，不能取 min , 因為會影響決策單調(diào)性
過程中爆了，但不一定是最優(yōu)的，結(jié)果可能不爆
8.
P6246 [IOI 2000] 郵局 加強(qiáng)版 加強(qiáng)版
典題， wqs 二分后決策單調(diào)性即可
浙公網(wǎng)安備 33010602011771號