Cho một dãy số nguyên gồm N phần tử nguyên A1, A2, …, AN.
Yêu cầu: Hãy trả lời Q truy vấn có dạng:
- i j: tính tổng các phần tử liên tiếp thuộc đoạn từ i đến j.
INPUT: QSUM.INP
Ø Dòng đầu tiên chứa 2 số nguyên dương N và Q (1 ≤ N, Q ≤ 105)
Ø Dòng thứ 2 chứa N số nguyên A1, A2, …, AN (|Ai| ≤ 103)
Ø Q dòng tiếp theo mỗi dòng chứa hai số nguyên i, j (1 ≤ i ≤ j ≤ N) thể hiện một câu hỏi truy vấn.
OUTPUT: QSUM.OUT
Ø Chứa Q dòng, mỗi dòng là câu trả lời truy vấn tương ứng trong INPUT.
Ví dụ:
QSUM.INP | QSUM.OUT | Giải thích ví dụ |
5 3 1 3 -4 5 -2 1 4 2 5 3 3 | 5 2 -4 | Dãy có 5 phần tử và 3 truy vấn - Truy vấn 1: tính tổng các phần từ thứ 1 đến thứ 4 là: 1 + 3 + (-4) + 5 = 5 - Tương tự như vậy ta được kết quả của 2 truy vấn còn lại là 2 và -4 |
* Ghi chú:
- Có 80% số test với dữ liệu cho là: 1 ≤ N, Q ≤ 5000.
Program HOC24;
var i,n,q,j,k,l: integer;
t: longint;
a: array[1..5000] of integer;
f1,f2: text;
const fi='QSUM.INP' ;
fo='QSUM.OUT' ;
begin
assign(f1,fi);
assign(f2,fo);
reset(f1);
rewrite(f2);
readln(f1,n,q);
for i:=1 to n do read(f1,a[i]);
readln(f1);
for k:=1 to q do
begin
readln(f1,i,j);
t:=0;
for l:=i to j do t:=t+a[l];
writeln(f2,t);
end;
close(f1);
close(f2);
end.
