あがいた梦を捨てて揺れる今日は眠って誤魔化せ

失くした言葉を知らないなら　各駅停车に乗り込んで

非常好凸包题，我不会一点。

首先尝试将答案写的形式化一点。令路径依次经过 $(i,a_i)$，则 $a_0=1,a_x=y,a_i\le a_{i-1}$，答案为

$$\sum_{i=1}^{x-1}{C_{a_i}}+\sum_{i=1}^{x}{(a_i-a_{i-1})i^2} =x^2y-1 +\sum_{i=1}^{x-1}{C_{a_i}-(2i+1)a_i} $$

令 $f_{i,j}$ 表示 $a_i=j$ 时的最小答案，根据斜率优化，决策点应该在 $(j,c_j)$ 的下凸包在斜率 $2i+1$ 的切点。

而我们注意到，随着 $i$ 的增大，$2i+1$ 也增大，那么决策点会单调右移。

如果从 $f_{x,y}$ 开始倒序模拟决策过程，那么就是在 $1\sim y$ 的下凸包上，先找到斜率 $2x+1$ 的切点 $p$，之后不断在 $p$ 原地决策，直到 $2i+1$ 小于 $p$ 与 $p-1$ 之间的斜率后，决策点会变为 $p-1$，然后重复……

注意到除了最开始的 $p$，再往后的决策是固定的，可以直接预处理贡献。而 $p$ 可以凸包二分求出，$p$ 的贡献也是容易计算的。

对于多组询问，注意到不同的只有 $y$ 的限制。考虑将询问离线挂到 $y$ 上，在维护到 $1\sim y$ 的凸包时计算答案。

时间复杂度 $O(q\log n)$。