B - Library Book Survey on the Bookshelf Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は図書館の司書として働いています。この図書館には N 個の本棚が一列に並んでおり、各本棚には 1 から N までの番号が付けられています。i 番目の本棚には A_i 冊の本が収められています。

青木君は図書館の蔵書調査を行うことになりました。青木君は Q 回の調査を行います。j 回目の調査では、本棚の番号の範囲として左端 L_j と右端 R_j を指定し、高橋君に L_j 番目から R_j 番目までのすべての本棚に収められている本の合計冊数を尋ねます。

各調査に対して、高橋君が報告すべき本の合計冊数を求めてください。

制約

  • 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
  • 1 行目には、本棚の個数を表す整数 N と、調査の回数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各本棚に収められている本の冊数を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 続く Q 行にわたって、各調査の範囲が与えられる。
  • そのうち j 行目（入力全体では 2 + j 行目、1 \leq j \leq Q）には、j 回目の調査で指定される範囲の左端 L_j と右端 R_j が、スペース区切りで与えられる。

出力

Q 行にわたって出力せよ。

  • j 行目 (1 \leq j \leq Q) には、j 回目の調査に対する答え、すなわち L_j 番目から R_j 番目までの本棚に収められている本の合計冊数を整数で出力せよ。

入力例 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

Score : 333 pts

Problem Statement

Takahashi works as a librarian at a library. The library has N bookshelves arranged in a row, numbered from 1 to N. The i-th bookshelf contains A_i books.

Aoki is going to conduct a collection survey of the library. Aoki will perform Q surveys. In the j-th survey, he specifies a range of bookshelf numbers with left endpoint L_j and right endpoint R_j, and asks Takahashi for the total number of books stored in all bookshelves from the L_j-th to the R_j-th.

For each survey, find the total number of books that Takahashi should report.

Constraints

  • 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)
  • All input values are integers

Input

N Q
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • The first line contains an integer N representing the number of bookshelves and an integer Q representing the number of surveys, separated by a space.
  • The second line contains integers A_1, A_2, \ldots, A_N representing the number of books stored in each bookshelf, separated by spaces.
  • The following Q lines give the range for each survey.
  • The j-th of these lines (the (2 + j)-th line of the entire input, 1 \leq j \leq Q) contains the left endpoint L_j and right endpoint R_j of the range specified in the j-th survey, separated by a space.

Output

Output Q lines.

  • The j-th line (1 \leq j \leq Q) should contain the answer to the j-th survey, namely the total number of books stored in the bookshelves from the L_j-th to the R_j-th, as an integer.

Sample Input 1

5 3
3 1 4 1 5
1 3
2 4
1 5

Sample Output 1

8
6
14

Sample Input 2

8 5
10 20 30 40 50 60 70 80
1 1
3 6
1 8
4 7
2 5

Sample Output 2

10
180
360
220
140

Sample Input 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

Sample Output 3

5711111109
1000000000
1
2611111110
500000000
3611111109
2100000000
4711111108