笔记重修计划一：斜率优化 dp & cdq 分治维护凸包（施工中）

施工中，但是目前暂停施工。

前言

刷 cdq 分治的时候做到了这题，发现自己不是很懂这个东西，跑回去看自己几个月前写的斜率优化 dp 笔记，当时认为自己弄得很明白了，但现在看来简直就是皮毛，遂弄明白后写下此文，希望自己之后有更多启发时能继续充实这篇文章。

若有不妥之处望指出。

如果单调？

设 \(f_i\) 表示第 \(i\) 天结束是最多能换来多少钱，为了方便转移设 \(x_i=f_i\frac{R_i}{A_iR_i+Bi}\) 表示用 \(f_i\) 的钱最多能换来多少张 A 券，\(x_i=f_i\frac{1}{A_iR_i+Bi}\) 表示用 \(f_i\) 的钱最多能换来多少张 B 券，那么不难写出转移式 \(f_i=\max\{f_{i-1}, \max\limits_{j<i}\{x_jA_i+y_jB_i\}\}\)。考虑什么情况下决策点 \(j\) 优于 \(k\)？钦定 \(x_j>x_k\)，那么 \(x_jA_i+y_jB_i>x_kA_i+y_kB_i \Rightarrow \frac{y_j-y_k}{x_j-x_k}> -\frac{A_i}{B_i}\)，注意这是保证了 \(x_j>x_k\) 的情况，如果不保证，式子会有所不同。

我们发现如果将决策点 \(j\) 对应的 \((x_j,y_j)\) 看作点，那么 \(\frac{y_j-y_k}{x_j-x_k}\) 就是 \(j,k\) 间的线段斜率，设它为 \(\text{slope}(j,k)\)，而由 \(j\) 优于 \(k\) 的条件，我们发现一个有效的决策点集应该会以一个斜率单调递减的上凸壳分布（将 \((x_j,y_j)\) 看作点），如果保证插入的点的 \(x\) 坐标单调递增，那么我们每次只需要在凸壳的最右端插入即可，然后弹出无用的决策点以维护凸壳。但是我们发现这题中 \(x\) 没有单调性，不过我们先看看如果 \(x\) 单调递增怎么做。

现在已经维护出了一个上凸壳，然后我们在末端加入点 \((x_i,y_i)\)。

首先和末尾 \(p\) 比较，发现 \(p,p-1,i\) 组成了一个向下的三角形结构，这时候 \(p\) 无论何时都不如 \(i\) 了，于是把 \(p\) 弹出，此时判定三角形的条件就是 \(\text{slope}(p-1,p)<\text{slope}(p,i)\)

同理的，\(i\) 再和 \(p-1\) 比较，\(p-1,p-2,i\) 也组成了一个向下的三角形结构，于是弹掉 \(p-1\)，直到和 \(p-2\) 比较时不再满足该条件，将 \(i\) 加入凸壳尾部即可。插入单点维护凸壳的部分我们解决了。

接下来如何查询 \(f_i\) 呢？考虑决策点 \(j\) 优于 \(k\) 的条件是 \(x_j>x_k,\text{slope}(j,k)> -\frac{A_i}{B_i}\)，而在这个上凸壳上，线段斜率单调递减，于是我们会发现，对于一个 \(i\)，对它有效的决策点永远是凸壳上一段前缀，我们从 \(p=1\) 开始，从凸壳左部端点开始枚举，直到 \(\text{slope}(p+1,p)> -\frac{A_i}{B_i}\) 不再成立，此时的 \(p\) 就是 \(f_i\) 的最优决策点，而正好 \(x_{p+1}>x_p\)（凸壳上结点横坐标递增），所以直接这样判定是对的（为什么我一直要强调判定条件中的 \(x_j>x_k\) 呢？因为由于不等式转化中对变号的要求，如果 \(x_j<x_k\)，那么 \(j\) 优于 \(k\) 的判定条件会有所不同，这是一定要注意的；但是我们在维护凸壳时直接使用 \(\text{slope}\) 而不论 \(x\) 大小关系是没有问题的，因为维护上凸壳只涉及到斜率本身，和判定决策点优劣没有关系）。但是对于 \(f_{1\sim n}\) 的求值呢？这就要考虑到决策单调性了。如果满足 \(-\frac{A_i}{B_i}\) 单调递减，那么越往后 \(p\) 可以取到的位置就越靠右，便满足了决策单调性，假如 \(-\frac{A_i}{B_i}\) 单调递减，那么我们一开始只要维护一个决策点指针 \(p=1\)，然后只要 \(\text{slope}(p+1,p)>-\frac{A_i}{B_i}\)，\(p\) 就一直右移，用 \(p\) 更新该 \(f_i\)，然后接着这个 \(p\) 去下一个 \(f_i\)。

其实这也说明了斜率优化 dp 维护凸壳中单调栈和单调队列的区别，上述过程相对于在用一个单调队列维护，无论是单调栈还是单调队列，都有 \(x\) 的单增性，所以每次插入新的决策点都是在右端队尾插入，而询问的时候就要看判定条件 \(\text{slope} ? g_i\)（\(?\) 代表 \(<,>,\le,\ge\) 等关系符号） 中 \(?\) 是什么以及该凸壳对应的 \(\text{slope},g\) 的单调性了。以 \(?\) 为 \(>\) 为例，比如上凸壳，\(g\) 单调递减，也就是这道题对应的情况，就得从队首找决策点，在队尾插入决策点，所以要用（双端）单调队列，同样要用单调队列的还有下凸壳 \(g\) 单调递增；如果上凸壳 \(g\) 单调递增或下凸壳，\(g\) 单调递减，那么决策点从队尾插入，也直接从队尾开始找，所以直接用只维护队尾的单调栈即可。

如果满足了插入的决策点中 \(x\) 的单调性以及询问的点中 \(-\frac{A_i}{B_i}\) 的单调性，那么我们就可以在 \(\mathcal{O}(n)\) 时间内求出 \(f_{1\sim n}\)。

制造单调？

但是这题不仅 \(x\) 不单调，\(-\frac{A_i}{B_i}\) 也不单调，那怎么办？有一种可以“制造单调性”的处理方式——cdq 分治。我们通过对 \(1\sim n\) 的 cdq 分治，将问题转化为编号在 \([l,mid]\)内的决策点对 \(f_{mid+1\sim r}\) 的影响，那么我们发现，这时候虽然还是没有单调性，但是我们就可以对两部分分别随意排序制造单调性了。对 \([l,mid]\) 内的决策点 \((x_i,y_i)\) 按照 \(x\) 从小到大排序，对 \((mid,r]\) 内的点按照 \(-\frac{A_i}{B_i}\) 从大到小排序，那么我们就能按照有单调性的那种的解决方式，先对 \([l,mid]\) 建出上凸壳，然后从 \(p=1\) 作为决策点开始求 \(f_{mid+1\sim r}\) 得到的贡献，就可以在 \(\mathcal{O}(n\log n)\) 时间内解决该题了。

具体分治的时候，为了不要再在分治内部排序导致变成 \(\mathcal{O}(n\log^2 n)\)，提前将点按照 \(-\frac{A_i}{B_i}\) 从大到小排序，然后分治完就把两部分按照 \(x\) 递增归并即可，为了保证下标的正确排序前记录一个 \(id\) 表示原下标。然后还有要用 \(f_{i-1}\) 更新 \(f_i\)，在递归到 \(l=r\) 时，也就是 \(f_i\) 求好了的时候，\(f_i\gets \max(f_{i-1},f_i)\)，并求出 \(x_i,y_i\)。

Submission

另解？

我们再回去看转移式 \(f_i=\max\{f_{i-1}, \max\limits_{j<i}\{x_jA_i+y_jB_i\}\}\)，先不看 \(f_{i-1}\)，后面的东西可以转化为 \(B_i\times(x_j\frac{A_i}{B_i}+y_j)\)，如果将 \(j\) 对应一条直线 \(l_j=x_j\times X+y_j\)，那么转移式相当于再求 \(l_{1\sim j-1}\) 中横坐标 \(\frac{A_i}{B_i}\) 取到的纵坐标最大值。可以李超线段树，对 \(\frac{A_i}{B_i}\) 离散化一下就可以了，时间复杂度也是 \(\mathcal{O}(n\log n)\)，全局插入直线单点查询最值。