寫在前面：

表面上我是有斜率的 \(O(n),o(n \log n),o(n\log^2n)\)。
其實統統是 \(O(n \log n)\) 的李超樹版子，嘻嘻。

下面是正文：

斜率優化，一種dp的優化方式，找到一個式子為 \(y=k*x+b\) 的玩意時就可以使用。
通過例題講解：

1. P2120 [ZJOI2007] 倉庫建設
   
   

你發現,你只會取連續的一段,而且不會限制你最后取了多少段,每一段在取了后其值就不會發生變化了.

然后這個一段的戰斗力 \(X\) 顯然可以作前綴和, \(X=Sum_r-Sum_l\)

那么基礎的dp式子就很明顯了:
第一個式子一定要看懂!

你發現把式子變成了三個部分:

• 又有 \(i\) 又有 \(j\) 的
• 只有 \(j\) 的
• 有了 \(i\) 就可以 \(O(1)\) 直接算的(前面怎么變其都不會變)

你在發現一下,實際上對于一個數 \(sum_i\) 影響其取值的就是這個數乘上一個數在加上一個固定的數
很明顯了, \(y=kx+b\) 其中y是取值最大值

想一想李超線段樹是干嘛的)

維護區間最大的線段!
你把這個玩意維護出來,不就做完了).管你什么單增,什么單減,什么不增,什么凸包,和我的輪椅說去吧!

每次更新了 \(f_i\) 又把 \(f_i\) 這條直線的斜率更新出來,再做下一個的查詢

再記錄一下我的李超樹版子:

struct Node{
	lb k,b;//取特定位置的值
	inline lb gy(int x){return (lb)x*k+b;}
}t[M];//定義函數
inline void upt(int id,int l,int r,Node New){
	int Mid=(l+r)>>1;//中間
	//左和中間互相比大小
	bool ql=New.gy(l)>t[id].gy(l),
		 qm=New.gy(Mid)>t[id].gy(Mid);
	//如果新的在中間更優,這個變成新的,流放舊的
	if(qm) std::swap(t[id],New);
	if(l==r) return void();
	//qm=1 流放原來的
	//ql=0 原來的在左邊大,滾去更新左邊
	//ql=1 原來的在左邊小,滾去更新右邊
	//qm=0 現在的接著流放
	//ql=0 現在的在左邊小,滾去更新右邊
	//ql=1 原來的在左邊大,滾去更新左邊
	if(ql!=qm) upt(ls,l,Mid,New);
	else upt(rs,Mid+1,r,New);
}
inline lb ask(int id,int l,int r,int x){
	if(l==r) return t[id].gy(x);
	int Mid=(l+r)>>1;
	//基礎定義往下搜
	if(x<=Mid) return max(t[id].gy(x), ask(ls,l,Mid,x));
	else return max(t[id].gy(x), ask(rs,Mid+1,r,x));
}

一些練手的題

記得一些題要離散化)

1. P3628 [APIO2010] 特別行動隊
   版子
2. P3648 [APIO2014] 序列分割
   版子
3. P2120 [ZJOI2007] 倉庫建設
   版子
4. P4360 [CEOI 2004] 鋸木廠選址
   你去搜一下\(f_1,f_2,f_3\) 表示在這里建第幾個工廠的最小花銷,反正最多沖兩個工廠
5. P4072 [SDOI2016] 征途
   方差式子自己推,發現最后的那個答案式子會非常簡單
6. P2900 [USACO08MAR] Land Acquisition G
   以max排序推獅子,要注意自己娶自己