潍坊网站制作推广ui设计到底能不能学
时间有点仓促，过几天会补。
来自 czz 学长的课，SMWC -> Day4 。
目录
- 凸函数介绍
- WQS二分
- 1. P2619【国家集训队 2】Tree I
- 2. CF739E Gosha is hunting
- 闵可夫斯基和
- 1. QOJ-5421 Factories Once More
- 2. GD 省集 tower
- Slope Trick
- 1. CF713C
- 2. ABC217H
- 3. [APIO2016] 烟火表演
- 总结
凸函数介绍
凸函数即为一阶导单调的函数，在 OI 中通常体现为差分后单调的函数。这类具有凸性的问题在最优化问题中十分常见，通常具有其对应的线性规划或者费用流模型，也通常使用反悔贪心或者模拟费用流等方法解决。
WQS二分
详见 this 。
有一类问题，通常具有“选择恰好 k k k 个”的标志，但是在 d p dp dp 状态中记录 k k k 复杂度又太高，此时通常使用 WQS二分 解决。
WQS二分 使用的前提为问题关于选择个数 k k k 具有凸性。
1. P2619【国家集训队 2】Tree I
模板题
2. CF739E Gosha is hunting
凸性还可以联系到网络流，比如这题。
建立网络流模型，然后模拟网络流做法。 O ( n l o g n ) O(nlogn) O(nlogn)
闵可夫斯基和
( m i n , + ) (min, +) (min,+) 和 ( m a x , + ) (max, +) (max,+) 卷积是常见的凸函数卷积，不难证明两个凸函数经过这样的卷积之后仍然是凸函数。（且这样的卷积常见于背包）
闵可夫斯基和常与分治等手段结合。
( m a x , + ) (max,+) (max,+) 卷积： f ( i ) = m a x j + k = i ( g ( j ) + h ( k ) ) f(i) = max_{j+k=i} (g(j) + h(k)) f(i)=maxj+k=i(g(j)+h(k)) 。
1. QOJ-5421 Factories Once More
考虑 树形dp，设 f u , i f_{u,i} fu,i 表示 u u u 子树内选了 i i i 个点的最大值。容易得到 d p dp dp 转移方程， f u , i = m a x j + k = i f u , j + f v , k + j × k × w ( u , v ) f{u,i} = max_{j+k=i} f_{u,j} + f_{v,k} + j \times k \times w(u, v) fu,i=maxj+k=ifu,j+fv,k+j×k×w(u,v)
发现为凸函数，可以通过 ( m a x , + ) (max,+) (max,+) 卷积做成闵可夫斯基和的形式，进行加速 d p dp dp 。
2. GD 省集 tower
不会。
用闵可夫斯基和可以做到 O ( n l o g n ) O(nlogn) O(nlogn) ，但是分类讨论的常数可达 81 81 81 倍。
Slope Trick
Slope Trick 是一种优化 d p dp dp 的方法。核心思想是储存 d p dp dp 转移的关键信息（如分段函数的分界点）然后利用数据结构高效维护转移。
例如凸函数，我们只需维护初始的斜率，初始的值和斜率的变化点即可。
常见的维护操作有：函数相加，找最值，加一个一次函数，取前后缀max，平移，翻转等。
1. CF713C
经典模板题。
2. ABC217H
弄一个暴力 d p dp dp ，设 f i , j f_{i,j} fi,j 表示 T i T_i Ti 时刻角色在 j j j 可能的最小伤害，转移就枚举上一次在哪：
f i , j = m i n j k + l e n = j − l e n f i − 1 , k + [ ( j > X i ) = D i ] × ∣ j − X fi,j = minjk+len=j−lenfi−1,k + [(j > Xi) = Di] × |j − X fi,j=minjk+len=j−lenfi−1,k+[(j>Xi)=Di]×∣j−X
事件的贡献是一个下凸函数，发现转移是一个先平移后加一个下凸函数的形式，不难验证仍然 fi 仍然是一个下凸函数。考虑用两个堆分别维护拐点。由于是下凸函数，则最小值的左边是单调递减，最小
值的右边是单调递增。则只需把维护最小值左边的拐点位置统一减去 len，最小值右边的拐点位置统一加上 len 即可。加上的函数很明显拐点只有一个 Xi，插入拐点然后维护堆的大
小即可。
3. [APIO2016] 烟火表演
又不会。
总结
===