分数: 333 分
问题陈述
高桥在一家图书馆担任图书管理员。图书馆有 N 书架排列成一排,编号从 1 to N。的 i第一个书架包含 A_i 书籍。
青木打算对图书馆进行一次藏书调查。青木将表演 Q 调查。在 j-第次调查,他指定了一系列带有左端点的书架编号 L_j 和右端点 R_j,并向 Takahashi 询问所有书架中存储的图书总数 L_j-第 R_j-th。
对于每项调查,找出 Takahashi 应报告的图书总数。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
- 所有输入值均为整数
输入
N Q A_1 A_2 \ldots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- 第一行包含一个整数 N 代表书架的数量和一个整数 Q 代表调查数量,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个书架存放的书籍数量,以空格分隔。
- 以下 Q 行给出了每个调查的范围。
- 的 j- 第这些行( (2 + j)整个输入的第行, 1 \leq j \leq Q) 包含左端点 L_j 和右端点 R_j 中指定的范围 j第次调查,以空格分隔。
输出
输出 Q 行。
- 的 j第行 (1 \leq j \leq Q) 应包含以下问题的答案 j第次调查,即书架中存放的图书总数 L_j-第 R_j-th,作为整数。
示例输入 1
5 3 3 1 4 1 5 1 3 2 4 1 5
示例输出 1
8 6 14
示例输入 2
8 5 10 20 30 40 50 60 70 80 1 1 3 6 1 8 4 7 2 5
示例输出 2
10 180 360 220 140
示例输入 3
10 8 1000000000 999999999 123456789 987654321 500000000 250000000 750000000 100000000 999999999 1 1 10 1 1 10 10 3 7 5 5 1 5 6 10 2 9
示例输出 3
5711111109 1000000000 1 2611111110 500000000 3611111109 2100000000 4711111108