题解

思路

递推的每一步从 $(i,j)$ 走到 $(i-1,j)$ 或 $(i-1,j-1)$。倒过来看，一个询问 $(x,y)$ 是从位置 $y$ 出发做 $x-1$ 次“原地或向左”移动，并把每次所在位置的 $a$ 值累加。

若路径最左到达 $l$，其中 $y-x+1\le l\le y$，则区间 $[l,y]$ 中每个位置至少访问一次，剩余的 $x-(y-l+1)$ 次访问应全部放在这个区间的最小值处。对最终最优的 $l$，可以把该最小值取为 $a_l$，于是候选答案为

$$\operatorname{sum}_y-\operatorname{sum}_l+a_l(x-y+l),$$

其中 $\operatorname{sum}_i=\sum_{j=1}^i a_j$。

做法

子任务 1：直接递推

按定义计算整个三角形：先令 $f(1,j)=a_j$，再按 $i$ 递增计算其余状态。预处理时间和空间均为 $O(n^2)$，每个询问 $O(1)$。

子任务 2：逐个枚举最左位置

枚举 $l\in[y-x+1,y]$，代入上式取最小值。预处理前缀和后，单次询问 $O(x)$，总复杂度 $O(\sum x)$，空间 $O(n)$。

子任务 3：线段树维护凸包

把候选式整理为

$$\operatorname{sum}_y+ \min_{y-x+1\le l\le y} \left(a_l(x-y)+a_l l-\operatorname{sum}_l\right).$$

每个位置 $l$ 对应直线

$$g_l(t)=a_l t+(a_l l-\operatorname{sum}_l),$$

询问需要在下标区间 $[y-x+1,y]$ 内、横坐标 $t=x-y$ 处求直线最小值。

在线段树每个结点中保存该下标区间全部直线的下凸包。建树时按斜率排序并删除永远不可能最优的直线；查询凸包时，直线值呈单谷形，可二分相邻值找到最小者。一个下标区间被拆成 $O(\log n)$ 个线段树结点，每个凸包查询再用 $O(\log n)$，因此总复杂度为

$$O(n\log n+m\log^2 n),$$

空间复杂度为 $O(n\log n)$。

所有乘法和前缀和均使用 64 位整数；判断三条直线冗余时使用 128 位整数避免交叉乘法溢出。

复杂度

• 子任务 1：时间 $O(n^2+m)$，空间 $O(n^2)$。
• 子任务 2：时间 $O(n+\sum x)$，空间 $O(n)$。
• 满分算法：时间 $O(n\log n+m\log^2 n)$，空间 $O(n\log n)$。