Nhập số nguyên dương N. Sau đó nhập 1 dãy a gồm N phần tử. Bạn được cho m truy vấn, mỗi truy vấn cung cấp 2 số x, y, yêu cầu bạn phải tính tổng đoạn con liên tiếp từ a[x] đến a[y]
Input
· Dòng đầu là số nguyên N (0 < n < 106)
· Dòng sau gồm n số nguyên a1, a2, ..., an. (|ai|<1000)
· Dòng tiếp theo là số nguyên dương m (0 < m < 106)
· M dòng tiếp theo, mỗi dòng ghi 2 số x, y (1 ≤ x ≤ y ≤ n)
Output: Xuất m dòng, dòng thứ i là kết quả của truy vấn thứ i.
Input
6
-1 8 -3 -1 8 -7
2
2 5
4 6
Output
12
0
Code C++: Độ phức tạp O(N)
Trả lờiXóa#include
#define ll long long
using namespace std;
ll S[1000006];
int n, m;
int main() {
freopen("inp.txt", "r", stdin);
freopen("out.txt", "w", stdout);
scanf("%d", &n); S[0]=0;
for(int i=1; i<=n; i++) {
int x;
scanf("%d", &x); S[i]=S[i-1]+x;
}
scanf("%d", &m);
for(int i=1; i<=m; i++) {
int l, r;
scanf("%d%d", &l, &r);
cout << S[r]-S[l-1] << "\n";
}
return 0;
}
Uses crt;
Trả lờiXóaVar n,i,x,y,tong:longint;
f:array[1..10000] of longint;
Begin
readln(n);
For i:=1 to n do
readln(f[i]);
readln(x);
readln(y);
For i:=x to y do
tong:=tong+f[i];
Write(tong);
readln;
end.
program p;
Trả lờiXóauses crt;
var a:array[1..100] of longint;
i,j,n,m,x,y,t:integer;
begin
clrscr;
readln(n);
for i:=1 to n do read(a[i]);
readln(m);
for j:=1 to m do
begin
readln(x,y);
for i:=x to y do t:=t+a[i];
write(t);
t:=0;
end;
readln;
end.