题意理解 我们有一个 N × M N×M 的网格，从 ( 1 , 1 ) (1,1) 出发，可以：

从 ( x , y ) (x,y) 到 ( x , y + 1 ) (x,y+1)，代价 x 2 x 2 （向右）

从 ( x , y ) (x,y) 到 ( x + 1 , y ) (x+1,y)，代价 c y c y ​ （向下）

有 Q Q 次询问，求到 ( x i , y i ) (x i ​ ,y i ​ ) 的最小代价。

N N 最大 10 9 10 9 ，不能直接 DP

M M 最大 2 × 10 5 2×10 5 ，列数较少

Q Q 最大 2 × 10 5 2×10 5

初步分析 设 d p [ x ] [ y ] dp[x][y] 表示到 ( x , y ) (x,y) 的最小代价。

转移：

d p [ x ] [ y ]

min ⁡ { d p [ x ] [ y − 1 ] + x 2 (从左边来) d p [ x − 1 ] [ y ] + c y (从上面来) dp[x][y]=min{ dp[x][y−1]+x 2

dp[x−1][y]+c y ​

​

(从左边来) (从上面来) ​

边界： d p [ 1 ] [ 1 ]

0 dp[1][1]=0。

但 N N 太大，不能直接计算所有 x x。

观察 对于固定的 y y，考虑 d p [ x ] [ y ] dp[x][y] 关于 x x 的变化。

从 y − 1 y−1 到 y y 时，代价是 x 2 x 2 ，所以从不同 x x 在 y − 1 y−1 列转移到 y y 列时，代价是 d p [ x ] [ y − 1 ] + x 2 dp[x][y−1]+x 2 。

从上面下来的代价是 d p [ x − 1 ] [ y ] + c y dp[x−1][y]+c y ​ 。

这其实是一个 动态规划与凸壳优化 的经典形式。

问题转化 我们考虑 从某一列到下一列 的转移。

假设我们已经知道第 y − 1 y−1 列的所有 d p [ x ] [ y − 1 ] dp[x][y−1]，那么在第 y y 列：

d p [ x ] [ y ]

min ⁡ ( d p [ x ] [ y − 1 ] + x 2 ,

d p [ x − 1 ] [ y ] + c y ) dp[x][y]=min(dp[x][y−1]+x 2 , dp[x−1][y]+c y ​ ) 但注意：从上往下的转移是 单调的（只能向下走），所以我们可以按 x x 从小到大计算。

更清晰的思路 定义 f y ( x )

d p [ x ] [ y ] f y ​ (x)=dp[x][y]。

那么：

f y ( x )

min ⁡ ( f y − 1 ( x ) + x 2 ,

f y ( x − 1 ) + c y ) f y ​ (x)=min(f y−1 ​ (x)+x 2 , f y ​ (x−1)+c y ​ ) 并且 f 1 ( 1 )

0 f 1 ​ (1)=0，对于 x

1 x>1， f 1 ( x )

∞ f 1 ​ (x)=∞（因为第一列只能从(1,1)往下走）。

关键观察 对于每个 y y， f y ( x ) f y ​ (x) 是一个 分段二次函数 的形式，并且是 凸函数（因为 x 2 x 2 是凸的，加上 min 和线性项保持凸性）。

我们可以维护每个 y y 的 f y ( x ) f y ​ (x) 的 分段表示，每段是一个二次函数或线性函数。

数学推导 假设在列 y y，我们有一些“决策点”，表示从列 y − 1 y−1 的某个 x x 直接向右走到当前列更优，而不是从上面下来。

设 g y − 1 ( x )

f y − 1 ( x ) + x 2 g y−1 ​ (x)=f y−1 ​ (x)+x 2 。

那么：

f y ( x )

min ⁡ ( g y − 1 ( x ) ,

f y ( x − 1 ) + c y ) f y ​ (x)=min(g y−1 ​ (x), f y ​ (x−1)+c y ​ ) 这个形式很像 斜率优化： 我们维护一个候选集合（即 g y − 1 ( x ) g y−1 ​ (x) 的凸包），然后与一个斜率为 c y c y ​ 的直线取 min。

凸包维护 对于每个 y y，我们维护一个凸包（在 x x 空间），表示 g y − 1 ( x ) g y−1 ​ (x) 的下凸壳。

g y − 1 ( x )

f y − 1 ( x ) + x 2 g y−1 ​ (x)=f y−1 ​ (x)+x 2

因为 f y − 1 ( x ) f y−1 ​ (x) 是凸的，加上 x 2 x 2 （凸）仍然是凸的，所以 g y − 1 ( x ) g y−1 ​ (x) 是凸的。

因此它的最小值可以在凸包上二分查找。

算法步骤 初始化： f 1 ( x ) f 1 ​ (x) 只在 x

1 x=1 有定义，值为 0。

对 y y 从 2 到 M M：

从 y − 1 y−1 的凸包（表示 g y − 1 g y−1 ​ ）得到当前列的最优起点

计算新的一列 f y ( x ) f y ​ (x) 的凸包

对每个询问 ( x i , y i ) (x i ​ ,y i ​ )，在 y i y i ​ 的凸包上二分找到 x i x i ​ 所在段，计算 f y i ( x i ) f y i ​

​ (x i ​ )。

实现细节 我们不需要存所有 x x，只需要存凸包的 断点（即分段点）。

对于每个 y y，我们维护：

一个列表 segments，每个元素是 (start_x, a, b) 表示这一段 f y ( x )

a x 2 + b x + c o n s t f y ​ (x)=ax 2 +bx+const？ 其实更简单：因为从左边来的代价是 x 2 x 2 ，从上面来的代价是线性 c y c y ​ ，所以 f y ( x ) f y ​ (x) 是分段二次或线性。

实际上，可以证明： f y ( x ) f y ​ (x) 是 分段二次函数，每段形式为 x 2 + α x + β x 2 +αx+β 或线性函数。

简化方法（官方解法思路） 定义 h y ( x )

f y ( x ) − x 2 h y ​ (x)=f y ​ (x)−x 2 。

那么转移变为：

h y ( x )

min ⁡ ( h y − 1 ( x ) ,

h y ( x − 1 ) + c y − ( 2 x − 1 ) ) h y ​ (x)=min(h y−1 ​ (x), h y ​ (x−1)+c y ​ −(2x−1)) 这里 2 x − 1 2x−1 来自 x 2 − ( x − 1 ) 2

2 x − 1 x 2 −(x−1) 2 =2x−1。

这样 h y ( x ) h y ​ (x) 是 分段线性 的，更容易用凸包维护。

最终算法（用 h y ( x ) h y ​ (x)） 初始化： h 1 ( 1 )

− 1 h 1 ​ (1)=−1（因为 f 1 ( 1 )

0 f 1 ​ (1)=0，减去 1 2 1 2 得 -1），其它为无穷大。

对 y y 从 2 到 M M：

将 h y − 1 h y−1 ​ 的凸包传递过来

在凸包上加一个斜率为 c y c y ​ 的直线，并调整截距（因为 c y − ( 2 x − 1 ) c y ​ −(2x−1) 中的 − 2 x −2x 会影响）

实际上更简单：我们维护 h y ( x ) h y ​ (x) 的凸包（下凸壳），每次加入新的候选点 ( x , h y − 1 ( x ) ) (x,h y−1 ​ (x))，并与从左边来的路径取 min。

具体实现时，用单调队列维护凸包点 ( x , v a l ) (x,val)，其中 v a l

h y ( x ) val=h y ​ (x)。

查询 对于查询 ( x i , y i ) (x i ​ ,y i ​ )，在 y i y i ​ 的凸包中二分找到 x i x i ​ 所在的线段，用线段公式计算 h y i ( x i ) h y i ​

​ (x i ​ )，然后 f y i ( x i )

h y i ( x i ) + x i 2 f y i ​

​ (x i ​ )=h y i ​

​ (x i ​ )+x i 2 ​ 。

复杂度 每列凸包操作均摊 O ( 1 ) O(1)

总 O ( M ) O(M) 构建

每个查询 O ( log ⁡ M ) O(logM) 二分

代码框架 cpp #include <bits/stdc++.h> using namespace std; using ll = long long;

struct Point { ll x, val; };

ll N, M, Q; vector c; vector<vector> hull; // hull[y] 存储凸包点

ll query(ll x, ll y) { // 在 hull[y] 中二分找到 x 所在的线段 // 返回 h_y(x) + x*x }

int main() { cin >> N >> M; c.resize(M + 1); for (ll i = 1; i <= M; i++) cin >> c[i];

hull.resize(M + 1);
// 初始化 y=1
hull[1].push_back({1, -1});

for (ll y = 2; y <= M; y++) {
    // 从 hull[y-1] 构建 hull[y]
    // 这里实现凸包合并与 min 操作
    // 略去具体实现
}

cin >> Q;
while (Q--) {
    ll x, y;
    cin >> x >> y;
    cout << query(x, y) << "\n";
}

} 总结 这道题的核心是：

将大规模网格 DP 转化为 凸包维护 问题

利用 h y ( x )

f y ( x ) − x 2 h y ​ (x)=f y ​ (x)−x 2 将代价转化为分段线性函数

用单调队列维护凸包，支持快速查询

最终答案 = h y ( x ) + x 2 h y ​ (x)+x 2

这样就能在 O ( M + Q log ⁡ M ) O(M+QlogM) 时间内解决，适用于 N N 高达 10 9 10 9 的情况。