Slope Trick
凸函数的封闭性
若 $ f $ , $ g $ 是凸函数，则 $ ( f + g ) $ 也是凸函数
若 $ f $ 是凸函数, $ g \in [0,+\infty] $，则 $ fg $ 也是凸函数
若 $ f $ , $ g $ 是凸函数，则 $ \max ( f , g ) $ 也是凸函数
卷积下确界
若 $ f $ , $ g $ 是凸函数，则 $ h(x) = \min_y ( f ( y ) + g ( x - y ) ) $ 也是凸函数
eg : 若 $ f $ 是凸函数，则 $ h(x) = \min_{ x - a \leq y \leq x + b } f ( y ) $ 也是凸函数
定义 $ g( x ) = \begin{cases}
0 , x \in [ - b , - a ]\
+\infty , \text{otherwise}
\end{cases}
$
则 $ h $ 是 $ f $ , $ g $ 的卷积下确界
斜率维护方式
-
直接维护拐点,用 $set$ 、堆等（一般斜率变化不大时使用）
-
维护每一段的左右端点和斜率，用李超线段树等
例题
[BalticOI 2004] Sequence (Day1)
设 $ dp $ 表示当前遍历到第 $ i $个数，选择的最大数 $ \leq j $ 时的最小代价
列出 $ dp $ 式 : $ dp_{i,j} = \min_{k=0}^{j-1} dp_{i-1,k} + | ( a_i - j ) | $
注意到每次整个 $dp$ 矩阵要向右平移一位，为了维持斜率值变化量在 $ [ 1 , n ] $ 之间，提出来单独处理；
拆分操作为：
-
加一个 " V " 形的函数
-
取前缀最小值
操作 $ 2 $ 实质上为将当前凹函数的所有 $ > 0 $ 的斜率段改为 $ 0 $ ，而操作 $ 1 $ 可以看成斜率比当前函数的负斜率段还要小的段斜率集体 $ -1 $ ，斜率比当前函数的负斜率段大的段斜率集体 $ + 1 $
两边都操作太麻烦，因为斜率段之间只有相对大小关系，于是，考虑直接将前者 $ -2 $
用堆维护，每次添加两次当前点，再弹出
操作：
原本的堆顶 $ 0 $ 在 $ +1 $ 之后变成了正斜率，应该被弹出
最后记录方案，显然每次弹出前的堆顶是当前点的最优决策
#include<bits/stdc++.h>
#define fre(s,i,j,k) for(int s=i;s<=j;s+=k)
#define rep(s,i,j,k) for(int s=i;s>=j;s-=k)
using namespace std;
const int N=1e6+5;
int n,ans[N];
long long answer;
priority_queue<int>ve;
main(){cin>>n;fre(i,1,n,1){int x;cin>>x;ve.push(x-i),ve.push(x-i);answer+=(ve.top()-(x-i)),ve.pop();ans[i]=ve.top();}cout<<answer<<"\n";rep(i,n-1,1,1)ans[i]=min(ans[i],ans[i+1]);fre(i,1,n,1)cout<<ans[i]+i<<"\n";
}
[NOISG 2018 Finals] Safety
和前一题相似，只不过这题要维护两个堆，分别为正斜率和负斜率
wqs 二分
考虑一个严格凸函数 $ f( x ) $ ，想要快速求解 $ f( x_0 ) $，但不好直接求
如果对于任意 $ k $ 能够快速求解 $ \min{{f( x ) - k x }} $ 以及 $ y = f( x ) $ 与 $ y = k x $ 的切点值 $ x_k $ ( $ x_k = \arg \min{{f( x ) - k x }} $ )
由于 $ f $ 是凸函数，则 $ x_k $ 关于 $ x $ 是单调递增的
二分 $ x_k $ ，若 $ x_k < x_0 $ ，则放大斜率，反之缩小，最后找到相切于 $ x_0 $ 的斜率 $ k_0 $ ，记此时求解出来的 $\min{{f(x)-k_0x}} = V(k_0) $ , 则 $f(x_0) = V(k_0) + k_0 x_0 $
例题
[国家集训队] Tree I
通过操作白边边权达到减少或增加白边数量的目的，二分额外边权即可
#include<bits/stdc++.h>
#define fre(s,i,j,k) for(int s=i;s<=j;s+=k)
#define rep(s,i,j,k) for(int s=i;s>=j;s-=k)
using namespace std;
using namespace FastIOS;
const int N=5e4+5,M=1e5+5,INF=1e9;
int n,m,need,fa[N];
struct Edge{int u,v,w,col;}ed[M];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
pair<bool,int>check(int val){fre(i,1,m,1)if(!ed[i].col)ed[i].w+=val;sort(ed+1,ed+m+1,[](Edge x,Edge y){return x.w==y.w?x.col<y.col:x.w<y.w;});int cnt=0,sum=0,cntb=0;fre(i,1,n,1)fa[i]=i;fre(i,1,m,1){int x=find(ed[i].u),y=find(ed[i].v);if(x!=y)fa[x]=y,cnt++,sum+=ed[i].w,cntb+=(!ed[i].col);if(cnt==n)break;}fre(i,1,m,1)if(!ed[i].col)ed[i].w-=val;return {cntb>=need,sum};
}
main(){n=rd(),m=rd(),need=rd();fre(i,1,m,1)ed[i]={rd()+1,rd()+1,rd(),rd()};int l=-INF,r=INF;while(l+1<r){int mid=(l+r)>>1;if(check(mid).first)l=mid;else r=mid;}wt(check(l).second-l*need);ios_end();
}