CF1787H
考虑减少量，设 \(a_i=b_i-a_i\)，那么减少的分数是 \(\min\{a_i, k \cdot t\}\)，我们要最小化之。
如果没有 \(a_i\) 的限制，按 \(k\) 排序取。考虑到 \(a_i\) 的限制，把数分开，如果顶到了限制丢到最后面是不劣的，因此把 \(k\) 从大到小排序做 dp，要么通过得到 \(kt\) 要么不通过得到 \(a_i\)。
\(f_{i, j} = \min\{f_{i-1, j}+a_i, f_{i-1, j-1} + k\cdot t\}\)。
题解告诉我们考虑 \(g_{i, j} = f_{i, j}-f_{i,j-1}\)，且 \(g_{i-1, j}\) 的增长速度快于 \(k_i \cdot j\)。
\(g_{i, j} = g_{i, j-1} + \min\{g_{i-1, j} + a_i, k_ij\} - \min\{g_{i-1, j-1}+a_i, k_i (j-1)\}\)
存在一个分界点，在其左边 \(f_{i-1, j}+a_i\) 更小，在右边 \(f_{i-1, j-1} + k_i \cdot j\) 更小。
平衡树维护差分数组，找分界点时需要找差分数组与 \(k_i \cdot j - a_i\) 的交点，进行单点插入以及后缀加即可。
abc305h
复合的顺序是按 \(b_i/(a_i-1)\) 排序后依次复合。
题解告诉我们代价关于段长度是凸的，做 wqs 二分即可。
至于代价怎么快速算，因为每一段复合起来不超过 \(C\)，最多只有 \(O(\log C)\) 个元素，可以直接枚举预处理。
另一位老哥告诉我们可以决策单调性分治，好像能懂，但不是很懂复杂度。
P9266
贡献满足四边形不等式。套路性进行 cdq，问题只有怎么求区间贡献。
建广义笛卡尔树，一边挪指针一边统计贡献，当然也可以广义笛卡尔树上斜率优化 dp，都太复杂。
这里的 cdq 有点意思，是强制中序转移的 cdq，算法流程大概形如：
-
处理 \([l, mid]\)
-
用 \([l, mid]\) 更新 \([mid+1, r]\)
-
处理 \([mid+1, r]\)
其中第二步是，先求出 \([mid+1, r]\) 中点的最优决策，再分治到两边继续求解，同层指针最多共扫一遍，因此指针移动次数是 \(O(n \log n)\) 的，\(n\) 为区间长度。
四边形不等式让我们可以做到每条斜线均摊 \(O(n)\)，总体 \(O(nm)\) 的优秀复杂度，不过这道题因为贡献无法快速算只能用挪指针的决策单调性分治。异层间可以打乱顺序比较方便，若同层则需要用钦定中序的 cdq 分治解决。
P9338
AB 内部的顺序不会变，变了肯定不好。
只要能排出 \(\leq k\) 的方案数就行了。
做 dp：\(f_{l, r}\) 表示匹配第 \([l, r]\) 个 A 的最少代价。有 \(w(l, r) = \sum \max\{0, b_i-l+1\}\)，其中 \(b_i\) 为第 \(i\) 个 A 前的 B 的个数。
\(c\) 是满足四边形不等式的，可以决策单调性分治。但事实上并不用那么麻烦。
显然 \(b_i\) 不减，找到一个位置 \(p\) 使得 \(b_i-l+1 > 0\)，于是式子是前缀和的形式，\(f_i = \min \{f_j + \sum_{k=p_j}^{i} (b_k-i+1)\} = \min \{f_j+S_b(i)-S_b(p_j-1)\}\)，可以斜率优化解决。
感觉斜率优化已经挺遥远了啊。别用斜率优化了，还是二分队列好理解。那么我们插入关于 \(j\) 的函数，任意两个函数最多一个交点，询问点也是单调的，于是按顺序维护将要成为答案的决策即可。
gym102331J
\(f_{u, i, 0/1}\)：根为 \(u\)，已经匹配 \(i\) 对，\(u\) 是否已经被匹配。
因为匹配可以构造成一个费用流模型，这是一个凸函数，因此可以做闵可夫斯基和，在链上分治 \(O(n \log n)\)。
否则进行轻重链剖分，轻链之间分治合并，重链用链的合并方法合并，复杂度不会算。
好像是经典的树上信息合并方法。仔细想想确实没用到什么性质。
gym102331H
怎么又是这道题啊。
一个著名的模拟费用流做法是每次取最大子段加入答案并将该子段全部取反，显然过不去。
但这告诉我们答案是凸的。线段树，每个节点维护一个函数，表示区间选 \(i\) 段的答案，为了合并需要记录是否包含左右端点，一个节点上四个函数。单次询问可以 wqs 二分，在每个节点存的函数那里二分找到切点并累加数值（求和函数的切点），单次是 \(O(\log^2 n)\) 的。
事实上可以离线后整体二分，这里整体二分的大概是切线斜率，于是可以在函数上挪指针了。整体二分中一层的一个函数最多被整体遍历一遍，于是总复杂度是 \(O(q \log n \log V)\) 的。
预处理的复杂度是 \(O(n \log n)\)。