自动搬运

查看原文

来自洛谷，原作者为

	s4CRIF1CbUbbL3AtIAly 僕だって空を飛べる / 雲になっていく / 風になっていく / いつかはみんな / 星になっていく

搬运于2025-08-24 23:09:39，当前版本为作者最后更新于2025-02-11 15:39:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先考虑 $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)$。