1D Country

题目描述

数轴上有 $N$ 个村庄。第 $i$ 个村庄位于坐标 $X_i$，有 $P_i$ 名村民。 回答 $Q$ 个查询。第 $i$ 个查询的格式如下：

给定整数 $L_i$ 和 $R_i$，求位于坐标在 $L_i$ 与 $R_i$ 之间（包含端点）的村庄中村民的总数。

输入格式

输入按照下述格式由标准输入给出： $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$ 个查询的答案。

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

1
5
10
0

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

26
15
7
26
18
28
26
11

提示

$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$ 所有输入值均为整数。考虑第一个查询。坐标在 $1$ 到 $1$ 之间的村庄是位于坐标 $1$ 的村庄，拥有 $1$ 名村民。因此，答案为 $1$。 考虑第二个查询。坐标在 $2$ 到 $6$ 之间的村庄是位于坐标 $3$ 和 $5$ 的村庄，分别有 $2$ 和 $3$ 名村民。因此，答案为 $2+3=5$.

标签: AtCoder|abc371D

来源

AtCoder|abc371D