← 返回题目列表

AtCoder · abc371_d

G. 1D 国家/地区

中文机器翻译题面 查看原题

分数: 350 点

问题陈述

有 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