[USACO21JAN] Minimum Cost Paths P

题目描述

Farmer John 的牧草地可以看作是一个$N×M$($2≤N≤10^9, 2≤M≤2⋅10^5$)的正方形方格组成的二维方阵(想象一个巨大的棋盘)。对于 $x∈[1,N],y∈[1,M]$,从上往下第 $x$ 行、从左往右第 $y$ 列的方格记为 $(x,y)$。此外,对于每一个 $y∈[1,M]$,第 $y$ 列拥有一个代价 $c_y$($1≤c_y≤10^9$)。 Bessie 从方格 $(1,1)$ 出发。如果她现在位于方格 $(x,y)$,则她可以执行以下操作之一: - 如果 $y<M$,Bessie 可以以 $x^2$ 的代价移动到下一列($y$ 增加一)。 - 如果 $x<N$,Bessie 可以以 $c_y$ 的代价移动到下一行($x$ 增加一)。 给定 $Q$($1≤Q≤2⋅10^5$)个独立的询问,每个询问给定 $(x_i,y_i)$($x_i∈[1,N],y_i∈[1,M]$),计算 Bessie 从 $(1,1)$ 移动到 $(x_i,y_i)$ 的最小总代价。

输入输出格式

输入格式


输入的第一行包含 $N$ 和 $M$。 第二行包含 $M$ 个空格分隔的整数 $c_1,c_2,…,c_M$。 第三行包含 $Q$。 最后 $Q$ 行每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。

输出格式


输出 $Q$ 行,为每个询问的答案。 注意本题计算中所使用的整数大小可能需要使用 64 位整数型(例如,C/C++ 中的 long long)。

输入输出样例

输入样例 #1

5 4
1 100 100 20
20
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
3 4
4 4
5 4

输出样例 #1

0
1
2
3
4
1
5
11
19
29
2
9
20
35
54
3
13
29
49
69

说明

#### 样例 1 解释 输出以方阵形式表示如下: ``` 1 2 3 4 *--*--*--*--* 1 | 0| 1| 2| 3| *--*--*--*--* 2 | 1| 5| 9|13| *--*--*--*--* 3 | 2|11|20|29| *--*--*--*--* 4 | 3|19|35|49| *--*--*--*--* 5 | 4|29|54|69| *--*--*--*--* ``` #### 测试点性质: - 测试点 1-3 满足 $N,M≤2000$。 - 测试点 4-8 满足 $c_2>c_3>⋯>c_M$。 - 测试点 9-15 满足 $N≤2⋅10^5$。 - 测试点 16-20 没有额外限制。 供题:Benjamin Qi