分数: 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