← 返回题目列表

AtCoder · awc0044_b

B. 图书馆书架上的图书调查

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

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