時間有點(diǎn)倉促，過幾天會補(bǔ)。
來自 czz 學(xué)長的課，SMWC -> Day4 。

凸函數(shù)介紹

凸函數(shù)即為一階導(dǎo)單調(diào)的函數(shù)，在 OI 中通常體現(xiàn)為差分后單調(diào)的函數(shù)。這類具有凸性的問題在最優(yōu)化問題中十分常見，通常具有其對應(yīng)的線性規(guī)劃或者費(fèi)用流模型，也通常使用反悔貪心或者模擬費(fèi)用流等方法解決。

---

WQS二分

詳見 this 。
有一類問題，通常具有“選擇恰好 $k$ 個”的標(biāo)志，但是在 $dp$ 狀態(tài)中記錄 $k$ 復(fù)雜度又太高，此時通常使用 WQS二分 解決。
WQS二分 使用的前提為問題關(guān)于選擇個數(shù) $k$ 具有凸性。

1. P2619【國家集訓(xùn)隊(duì) 2】Tree I

模板題

2. CF739E Gosha is hunting

凸性還可以聯(lián)系到網(wǎng)絡(luò)流，比如這題。
建立網(wǎng)絡(luò)流模型，然后模擬網(wǎng)絡(luò)流做法。$O(nlogn)$

---

閔可夫斯基和

$(min,+)$ 和 $(max,+)$ 卷積是常見的凸函數(shù)卷積，不難證明兩個凸函數(shù)經(jīng)過這樣的卷積之后仍然是凸函數(shù)。（且這樣的卷積常見于背包）
閔可夫斯基和常與分治等手段結(jié)合。

$(max,+)$ 卷積： $f(i)=ma{x}_{j+k=i}(g(j)+h(k))$ 。

1. QOJ-5421 Factories Once More

考慮 樹形dp，設(shè) $f_{u,i}$ 表示 $u$ 子樹內(nèi)選了 $i$ 個點(diǎn)的最大值。容易得到 $dp$ 轉(zhuǎn)移方程，$$fu,i=ma{x}_{j+k=i}{f}_{u,j}+f_{v,k}+j\times k\times w(u,v)$$
發(fā)現(xiàn)為凸函數(shù)，可以通過 $(max,+)$ 卷積做成閔可夫斯基和的形式，進(jìn)行加速 $dp$ 。

2. GD 省集 tower

不會。
用閔可夫斯基和可以做到 $O(nlogn)$ ，但是分類討論的常數(shù)可達(dá) $81$ 倍。

---

Slope Trick

Slope Trick 是一種優(yōu)化 $dp$ 的方法。核心思想是儲存 $dp$ 轉(zhuǎn)移的關(guān)鍵信息（如分段函數(shù)的分界點(diǎn)）然后利用數(shù)據(jù)結(jié)構(gòu)高效維護(hù)轉(zhuǎn)移。
例如凸函數(shù)，我們只需維護(hù)初始的斜率，初始的值和斜率的變化點(diǎn)即可。
常見的維護(hù)操作有：函數(shù)相加，找最值，加一個一次函數(shù)，取前后綴max，平移，翻轉(zhuǎn)等。

1. CF713C

經(jīng)典模板題。

2. ABC217H

弄一個暴力 $dp$ ，設(shè) $f_{i,j}$ 表示 $T_i$ 時刻角色在 $j$ 可能的最小傷害，轉(zhuǎn)移就枚舉上一次在哪：
$$fi,j=minjk+len=j?lenfi?1,k+[(j>Xi)=Di]\times |j?X$$
事件的貢獻(xiàn)是一個下凸函數(shù)，發(fā)現(xiàn)轉(zhuǎn)移是一個先平移后加一個下凸函數(shù)的形式，不難驗(yàn)證仍然 fi 仍然是一個下凸函數(shù)。考慮用兩個堆分別維護(hù)拐點(diǎn)。由于是下凸函數(shù)，則最小值的左邊是單調(diào)遞減，最小
值的右邊是單調(diào)遞增。則只需把維護(hù)最小值左邊的拐點(diǎn)位置統(tǒng)一減去 len，最小值右邊的拐點(diǎn)位置統(tǒng)一加上 len 即可。加上的函數(shù)很明顯拐點(diǎn)只有一個 Xi，插入拐點(diǎn)然后維護(hù)堆的大
小即可。

3. [APIO2016] 煙火表演

又不會。

總結(jié)

===