AT_abc371_d [ABC371D] 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$ 个查询的答案。

输入输出样例 #1

输入 #1

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

输出 #1

1
5
10
0

输入输出样例 #2

输入 #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

说明/提示

限制条件

• $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$ 的村庄，村民有 $1$ 人，因此答案为 $1$。
再看第 $2$ 个查询。坐标在 $2$ 以上且 $6$ 以下的村庄有坐标为 $3$ 和 $5$ 的村庄，村民分别为 $2$ 人和 $3$ 人，因此答案为 $2+3=5$。

由 ChatGPT 4.1 翻译