凸优化相关
考虑到
因为要最小化 \(\sum\limits_{i=1}^{m}\frac{num_i}{k_i}\) 所以用调整法可以说明 \((\sum\limits_{i=1}^{m}k_i sum_i)\) 会取其上界 \(1\)，这就把 \(\{k\}\) 给安排了。
只需要最小化右式子。再用调整法可以说明 sum 里面应该是连续的，于是可以先对 \(s\) 排序，然后按顺序做一个 dp。这实际上就转化成了一个限制区间个数的区间分拆问题
WQS 二分，引入一个惩罚参数 lambda，将问题转化为：不限制分组数，但每多一组就要付出 lambda 的代价。可以看出惩罚参数越大分组越少，所以我们大概是要求一个适当大的惩罚参数使得分组的组数不超过 \(m\)。
这里的四边形不等式貌似不能直接套结论把 \(\sqrt{x}\) 剥掉直接考虑 \(x\)，因为这里就是要考虑 \(w(i,j) = dp[i-1] + \sqrt{(j-i)(pre_{j} - pre_{i})} + \lambda\) 这样的 \(w\) 取 min，而不带负号 sqrt 并非下凸而是上凸。
当然这里还是只需要考虑 \(\sqrt{(j-i)(pre_{j} - pre_{i})}\) 是否满足四边形不等式。
直观地理解的话，把 \(pre_j\) 替换成 \(j\)，于是 \(w\) 刚好到 \(j-i\)，一个凸性的临界点。然后 \(pre\) 可能会再稍微下凸一点，即考虑到 \(\Delta pre\) 单调不减，就让这个 \(w\) 变成下凸的了。
然后就是一个典型的区间分拆问题，这类问题 听说 只要把四边形不等式证出来了，则可推出 Monge 最短路关于 经过的边数 \(k\)（即拆分组数）有下凸性。
这题貌似没有说清楚能不能让 \(num_i=0\)，即某个区间为空，即只需要区间数 \(\le m\) 而非恰好 \(m\)。但看起来通过一点调整可以说明组数越多越好。所以关于组数应该是一个下凸的减函数。
四边形不等式、区间包含单调性、决策单调性¶
要讨论的是这样的一类问题
关于某些 \(w\) 满足四边形不等式的证明：
(i)
把不等式写出来后，由于实质上只是左端点交换了一下，只与左端点有关的或者只与右端点有关的并不会改变，两边长得一样的，可以消去；常量更加可以消去了。 for example, 有时候 \(w(i,j)\) 可能会被替换成 \(w'(i,j) = dp[i-1] + w(i,j)\)，然而 \(dp[i-1]\) 这一项只与左端点有关，所以其是否满足四边形不等式并不会被改变。还有就像是 \(\lambda(j-i+1)\) 这种可以被拆成左、右端点独立作用的也会被消去。
(ii)
通过一点小技巧，可以发现 \(i<i+1\le j < j+1\) for \(j=j_0,j_0+1\) 满足四边形不等式 \(\implies\) \(i<i+1\le j < j+2\) 满足四边形不等式，同理可以如此扩展左端点。所以可以只证明左端点相差 \(1\) 与右端点相差 \(1\) 的情况。
(iii)
对于显式的、可求二阶导的下凸函数 \(f\)，\(w(i,j) := f(j-i)\)，证明则不需要这么麻烦。稍微推导可以发现无非是要说明对于 \(a< b\le c< d\) at the same time \(a+d = b+c\)，which actually represent the length of the 4 mentioned intervals，we have \(f(b) + f(c) \le f(a)+f(d)\)。FYI, there's a special interpretation on "intersect \(\le\) include", which is "equal \(\le\) different"。这样的话其实就是要说明 \(f(b) - f(a) \le f(d) - f(c)\)，然而 \(b-a = d-c\)，从而就是要说明 \(f(a+\Delta) - f(a) \le f(c+\Delta) - f(c)\)。这几乎就是下凸性质的定义。
(iv)
ref 决策单调性优化 dp 学习笔记 | Exber's Blog 上述性质似乎可以扩展（但没有提供证明），如果 \(w(l,r)\) 满足区间包含单调性和四边形不等式，\(f(x)\) 为下凸函数，则： - \(f(w(l,r))\) 满足四边形不等式 - 如果 \(f(x)\) 单调不降（也就是没有触底反弹那一段），则 \(f(w(l,r))\) 还满足区间包含单调性
(v)
还有一些问题，在考虑四边形不等式进行代数运算时，不妨考虑对于三个区间 \([l_1,l_2],[l_2,r_1],[r_1,r_2]\) 分别设一些变量，这样代数证明会明显一点。比如说证明 $$ f(s_1+s_2) + f(s_2+s_3) \le f(s_1+s_2+s_3) + f(s_2) $$
#2157. 「POI2011 R1」避雷针 Lightning Conductor - 题目 - LibreOJ
注意中途运算时 sqrt 相关操作不能取整，反之则会破坏 \(-\sqrt{x}\) 的下凸性（比如说相邻两项点值一样斜率就直接为 0 了）。
对于区间划分型 dp，听说 恰经过 \(k\) 条边蒙日矩阵最短路关于 \(k\) 是下凸的。
wqs 二分¶
洛谷题解质量有点差，很多都看不出和 wqs 二分有什么关系。 这样思考，设 \(g_x\) 是恰选中 \(x\) 条白边的最小权。那么 \(f(x) := g_x - \lambda x\) 就是给这 \(x\) 条白边的权值减去 \(\lambda\) 的惩罚代价后的权值，那么 \(g_x-\lambda x\) 的最小值在什么地方取到？这等价于提前给所有白边都减去 \(\lambda\)，然后跑 mst。这有什么意义呢？
考虑 \((need-1, g_{need-1})\) 和 \((need, g_{need})\)，当 \(\lambda\) 恰好等于这两个点的斜率时，如果能有下凸性，并且同取最小值的时候可以取 \(x\) 大的，这时候就会取到后面的那个作为最小值的 \(x\) 点（如果取到 \(>need\) 的其实同理可以往回取）。
当 \(\lambda\) 大于这两个点的斜率时，\(< need\) 的部分 比 大于等于 \(\ge need\) 的部分不优。
当 \(\lambda\) 大于这两个点的斜率时，\(< need\) 的部分 比 大于等于 \(\ge need\) 的部分更优。
所以二分这个惩罚代价，使得 \(p = \max\{pos : f(pos) = \min_{x}\{f(x)\}\}\) 位于 \(\ge need\) 部分，那么必然通过调整使得 \(f(need) = f(p)\)。
貌似有道更难一点的：P5633 最小度限制生成树 - 洛谷。
题解 P1912 【[NOI2009]诗人小G】 - 洛谷专栏
高维 wqs 二分¶
对于两维分别凸的函数，它的性质并不像一维的那么好。比如说对于一维情况，点 \(x\) 的斜率自然地表述成 \(x\) 和 \(x-1\) 对应的点所确定的直线的斜率；对于二维呢？是考虑 \((x,y)\) 与 \((x-1,y)\) 与 \((x,y-1)\) 构成的切平面吗？然而这个切平面未必能确定其与 \((x-1,y-1)\) 的关系。另外，在一维的时候我们遇到的共线问题，在高维会变得更复杂。总之这个升维并不是显然的。
这里需要引入一个不太容易想得到的对偶函数（Legendre 变换）：对于上凸的 \(f(x)\)，令
则可证明 \(g(k)\) 是下凸函数，且最小值在 \(k = f'(a)\) 时（离散情况则取离散定义，可能是一个区间，比如说 \(\left[ f(x+1)-f(x),f(x)-f(x-1) \right]\) 中每一个 \(k\)）取到，即 \(f(a)\)。
这个操作的直观是，对于一个 fixed 的 \(k\)，在上凸壳的不同的点去做这个斜率的直线，交到 \(x=a\) 的位置中，取最大的。实际上我们会发现，这个最大位置实际上取的就是直线与上凸壳的切点。
只有整个上凸壳的切线恰好在经过 \((a,f(a))\) 时，这个最大值才会取到下界 \(f(a)\)。为什么关于 \(k\) 会下凸呢？因为随着切点远离 \(x\)，\(\text{d}k\) 乘上这个距离会越来越大。
上面这种想法可以扩展。对于两维联合（这里只是另一维为常数意义下的话应该不太对的）上凸的 \(f(x,y)\)，现在想要单点求值，\(f(a,b)\)。那么只需要考虑由 \(k_1,k_2\) 构成的切平面，\(z = k_1 x + k_2 y\)（这里省略了一个常数 \(C\)，我们会假想 \(C\) 使得恰好与二维上凸壳相切的，但其实整体平移没有影响）
应该能有 \(g(k_1,k_2)\) 关于两维联合下凸，且最小值在 \((k_1,k_2) = \left( f'_x(a,b), f'_y(a,b) \right)\) 处取到。（或者离散情况下，可以是包含 \((a,b)\) 的某些平面的并）
联合下凸应该能保证，先预先对 fixed 的 \(x\) 找完 \(y\) 这维随便取后的最值，仍能在 \(x\) 方向有凸性。
上面的内容的严谨性还待我进一步阅读专业书籍。总之网上存在一些并不那么合适的论述，不当弱化了一些条件。
此外实现的时候不要忘记凸性取反。
反悔贪心¶
这个东西要想清楚，为什么被反悔的这个结点，不会递归地去找之前没有被匹配的点或者反悔的结点。（因为可以调整成当前这个点直接去找递归匹配或者反悔的结点，同时保持不劣，所以在前面已经被考虑到了）。
PA 2013 Raper - 洛谷（同 Problem - N - Codeforces Problem - O - Codeforces）
上面这个模型套一个 wqs 二分罢了。不过应该要在代价相同的时候区分新匹配点和反悔点，因为反悔不会增加 num，新匹配点会增加 num。（按我习惯的写法）wqs 二分应在代价相同的情况下，统一取一个最大的 num，如果这个 num 大于等于 k 就返回 true。这样能准确决策出 \(k\) 点所对应的斜率（如果最后二分出来的 num 大于 \(k\) 也没关系，这说明它对应的斜率和 \(k\) 点一样）
M-低谷(hard)中国地质大学（武汉）2024年新生赛（同步赛）
参答是反悔贪心。但我现在一眼能看出 (低谷数量, 所需消耗的最小代价) 的凸性（初始低谷数量），用 wqs 二分单点求值，然后从 初始低谷数量 到 \(\lfloor(n-1)/2\rfloor\) 这段是递增的，简单二分出最多的低谷数量即可。