/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
頂点に 1 から N+1 の番号がついた N+1 頂点の辺重み付き無向グラフが与えられます。
1 \leq i \leq N を満たす整数 i について、頂点 i と頂点 (i \bmod N) + 1 を結ぶ重み A_i の辺があります。
また、1 \leq i \leq N を満たす整数 i について、頂点 i と頂点 N+1 を結ぶ重み B_i の辺があります。これ以外の辺はありません。
Q 個のクエリを処理してください。クエリでは S, T が与えられるので、頂点 S から頂点 T への最短経路の長さを求めてください。
制約
- 3 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 10^9
- 1 \leq S \lt T \leq N+1
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
各クエリ \mathrm{query}_q は以下の形式で与えられる。
S T
出力
Q 行出力せよ。q 行目には q 番目のクエリの答えを出力せよ。
入力例 1
5 3 1 3 4 2 5 5 2 4 3 7 2 5 5 6 1 4
出力例 1
6 5 6
1 番目のクエリについて、頂点 2 から頂点 5 への最短経路の一つは 2\to1\to5 であり、その長さは A_1+A_5=1+5=6 です。
入力例 2
10 12 95786828 55052989 7398452 90695030 73248844 120697567 77915140 68865651 15301338 68674005 690874817 21524935 244587369 529970100 736247510 757265588 993115119 576136368 21553212 219853538 5 6 5 8 2 6 3 7 1 3 3 4 8 11 1 10 2 6 6 8 8 9 5 8
出力例 2
73248844 265090269 226395315 244911927 150839817 7398452 90418863 68674005 226395315 198612707 68865651 265090269
Score : 450 points
Problem Statement
You are given an edge-weighted undirected graph with N+1 vertices numbered 1 to N+1.
For each integer i satisfying 1 \leq i \leq N, there is an edge of weight A_i connecting vertex i and vertex (i \bmod N) + 1.
Also, for each integer i satisfying 1 \leq i \leq N, there is an edge of weight B_i connecting vertex i and vertex N+1. There are no other edges.
Process Q queries. In each query, you are given S and T; find the length of the shortest path from vertex S to vertex T.
Constraints
- 3 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 10^9
- 1 \leq S \lt T \leq N+1
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query \mathrm{query}_q is given in the following format:
S T
Output
Output Q lines. The q-th line should contain the answer to the q-th query.
Sample Input 1
5 3 1 3 4 2 5 5 2 4 3 7 2 5 5 6 1 4
Sample Output 1
6 5 6
For the first query, one shortest path from vertex 2 to vertex 5 is 2\to1\to5, and its length is A_1+A_5=1+5=6.
Sample Input 2
10 12 95786828 55052989 7398452 90695030 73248844 120697567 77915140 68865651 15301338 68674005 690874817 21524935 244587369 529970100 736247510 757265588 993115119 576136368 21553212 219853538 5 6 5 8 2 6 3 7 1 3 3 4 8 11 1 10 2 6 6 8 8 9 5 8
Sample Output 2
73248844 265090269 226395315 244911927 150839817 7398452 90418863 68674005 226395315 198612707 68865651 265090269