103713: [Atcoder]ABC371 D - 1D Country

Problem Statement

There are $N$ villages on a number line. The $i$-th village is located at coordinate $X_i$, and has $P_i$ villagers.

Answer $Q$ queries. The $i$-th query is in the following format:

• Given integers $L_i$ and $R_i$, find the total number of villagers living in villages located between coordinates $L_i$ and $R_i$, inclusive.

Constraints

• $1\leq N,Q\leq 2\times 10^5$
• $-10^9\leq X_1 < X_2 < \ldots < X_N \leq 10^9$
• $1\leq P_i\leq 10^9$
• $-10^9\leq L_i \leq R_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$X_1$ $\ldots$ $X_N$
$P_1$ $\ldots$ $P_N$
$Q$
$L_1$ $R_1$
$\vdots$
$L_Q$ $R_Q$

Output

Print $Q$ lines.

The $i$-th line$(1\leq i \leq Q)$ should contain the answer to the $i$-th query.

Sample Input 1

4
1 3 5 7
1 2 3 4
4
1 1
2 6
0 10
2 2

Sample Output 1

1
5
10
0

Consider the first query. The villages between coordinates $1$ and $1$ are the village at coordinate $1$, with $1$ villager. Hence, the answer is $1$.

Consider the second query. The villages between coordinates $2$ and $6$ are the villages at coordinates $3$ and $5$, with $2$ and $3$ villagers, respectively. Hence, the answer is $2+3=5$.

Sample Input 2

7
-10 -5 -3 -1 0 1 4
2 5 6 5 2 1 7
8
-7 7
-1 5
-10 -4
-8 10
-5 0
-10 5
-8 7
-8 -3

Sample Output 2

26
15
7
26
18
28
26
11

问题陈述

在一条数线上有$N$个村庄。第$i$个村庄位于坐标$X_i$，并且有$P_i$个村民。

回答$Q$个查询。第$i$个查询的格式如下：

• 给定整数$L_i$和$R_i$，找出位于坐标$L_i$和$R_i$之间（包括）的村庄中的村民总数。

约束条件

• $1\leq N,Q\leq 2\times 10^5$
• $-10^9\leq X_1 < X_2 < \ldots < X_N \leq 10^9$
• $1\leq P_i\leq 10^9$
• $-10^9\leq L_i \leq R_i \leq 10^9$
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

$N$
$X_1$ $\ldots$ $X_N$
$P_1$ $\ldots$ $P_N$
$Q$
$L_1$ $R_1$
$\vdots$
$L_Q$ $R_Q$

输出

打印$Q$行。

第$i$行（$1\leq i \leq Q$）应包含对第$i$个查询的答案。

示例输入 1

4
1 3 5 7
1 2 3 4
4
1 1
2 6
0 10
2 2

示例输出 1

1
5
10
0

考虑第一个查询。位于坐标$1$和$1$之间的村庄是坐标为$1$的村庄，有$1$个村民。因此，答案是$1$。

考虑第二个查询。位于坐标$2$和$6$之间的村庄是坐标为$3$和$5$的村庄，分别有$2$和$3$个村民。因此，答案是$2+3=5$。

示例输入 2

7
-10 -5 -3 -1 0 1 4
2 5 6 5 2 1 7
8
-7 7
-1 5
-10 -4
-8 10
-5 0
-10 5
-8 7
-8 -3

示例输出 2

26
15
7
26
18
28
26
11