/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
N 個のマスが一直線上に並んでおり、左から順に 1, 2, \ldots, N の番号が付いています。
あなたがマス i にいるとき、以下のいずれかの移動をすることができます。
-
1 \leq j < i なる整数 j を選び、マス j に移動する。この移動にはコストが L_i かかる。
-
i < j \leq N なる整数 j を選び、マス j に移動する。この移動にはコストが R_i かかる。
Q 個のクエリが与えられます。それぞれについて答えてください。各クエリは以下の形式です。
- 整数 s, t が与えられる。あなたがマス s から移動を繰り返してマス t に辿り着くまでに必要なコストの合計の最小値を求めよ。
制約
- 2 \leq N \leq 3 \times 10^5
- 1 \leq Q \leq 3 \times 10^5
- 1 \leq L_i \leq 10^9 (2 \leq i \leq N)
- 1 \leq R_i \leq 10^9 (1 \leq i \leq N - 1)
- 各クエリについて 1 \leq s, t \leq N
- 各クエリについて s \neq t
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N Q
L_2 L_3 \ldots L_N
R_1 R_2 \ldots R_{N - 1}
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
ただし、\text{query}_i は i 番目のクエリであり、以下の形式で与えられる。
s t
出力
Q 行出力せよ。
i 行目には、i 番目のクエリに対する答えを出力せよ。
入力例 1
5 7 5 6 2 9 3 1 3 8 1 2 2 1 2 4 3 2 3 5 4 3 5 2
出力例 1
3 3 1 5 3 2 9
1, 2 番目のクエリについて説明します。
1 番目のクエリでは、マス 1 から直接マス 2 に移動したとき、コストの合計は R_1 = 3 となり、これがコストの合計として考えられる最小値になります。
2 番目のクエリでは、マス 2 からマス 4 に移動し、その後マス 4 からマス 1 に移動したとき、コストの合計は R_2 + L_4 = 3 となり、これがコストの合計として考えられる最小値になります。
Score : 400 points
Problem Statement
There are N squares arranged in a row, numbered 1, 2, \ldots, N from left to right.
When you are on square i, you can make one of the following moves.
-
Choose an integer j such that 1 \leq j < i, and move to square j. The cost of this move is L_i.
-
Choose an integer j such that i < j \leq N, and move to square j. The cost of this move is R_i.
You are given Q queries. Answer each of them. Each query is in the following format.
- Integers s and t are given. Find the minimum total cost required to reach square t from square s by repeatedly making moves.
Constraints
- 2 \leq N \leq 3 \times 10^5
- 1 \leq Q \leq 3 \times 10^5
- 1 \leq L_i \leq 10^9 (2 \leq i \leq N)
- 1 \leq R_i \leq 10^9 (1 \leq i \leq N - 1)
- 1 \leq s, t \leq N for each query.
- s \neq t for each query.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q
L_2 L_3 \ldots L_N
R_1 R_2 \ldots R_{N - 1}
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
Here, \text{query}_i is the i-th query, given in the following format:
s t
Output
Output Q lines.
The i-th line should contain the answer to the i-th query.
Sample Input 1
5 7 5 6 2 9 3 1 3 8 1 2 2 1 2 4 3 2 3 5 4 3 5 2
Sample Output 1
3 3 1 5 3 2 9
We explain the first and second queries.
For the first query, if you move directly from square 1 to square 2, the total cost is R_1 = 3, which is the minimum possible total cost.
For the second query, if you move from square 2 to square 4 and then from square 4 to square 1, the total cost is R_2 + L_4 = 3, which is the minimum possible total cost.