题解：P11706 「KTSC 2020 R1」穿越

· · 题解

首先考虑 A 和 B 固定怎么做。

从右往左做，记 dp_{i,j} 表示考虑到第 i 列时第 j 行的最优答案。

容易发现转移可以写成一个区间加和全局取 \min 的形式，因此可以线段树优化。具体来说，对于第 i 列先使 [l_i,r_i] 加上 B，接下来查询全局 \min，加上 A 之后令所有数与它取 \min。

回到原题，此时 A 和 B 不固定。注意到所有方案都可以写成 x 次 A 操作 和 y 次 B 操作，那么每次询问给出 A,B 等价于查询 Ax+By 的最小值。

因为 A,B 都是正的，所以可以求出 (x,y) 构成的左下凸壳，查询时直接在凸包上二分。

如何求出左下凸壳呢？可以参考 P6158 等最小乘积模型的题目中的方法（记 calc(A,B) 表示 Ax+By 最小的解 (x,y)）：

最初用 calc(1,0) 和 calc(0,1) 找出最靠左和最靠下的点，它们是左下凸壳的两端。之后对于任意两个点 A,B，考虑找出离 AB 最远的点 C。这可以写成叉积形式，只保留与 C 有关的项之后可以得到 C=calc(y_A-y_B,x_B-x_A)。如果此时 C 在直线 AB 上说明凸壳上这两点之间不存在其他点，于是结束，否则分治处理 A,C 和 C,B。

整点凸包点数的量级是 O(n^\frac 23) 的，因此总复杂度 O(n^\frac 53\log n+q\log n)。