內容
給定一個長度為 n 的整數序列 A，請回答 q 筆詢問。每筆詢問會問其中一段連續區間的總和為何。
輸入
輸入的第一行有一個整數 n (1 <= n <= 200000)，代表 A 序列的長度。
第二行有 n 個整數以空白分隔，依序表示 A 序列中的數字，其中數字的絕對值不會超過 10^9。
第三行有一個整數 q (1 <= n <= 200000)，代表詢問的數量。
接下來有 q 行，每行有兩個個數字 l, r，表示詢問為序列 A 中第 l 個數字到第 r 個數字的總和。
5
1 2 3 4 5
3
1 3
2 4
3 5
輸出
輸出 q 行，每行有一個整數表示該次詢問的答案。
6
9
12
解題思路
由於計算 list[a] ~ list[b] 的範圍時是連續不中斷的相加，所以在建立陣列時用相加的方式，每一項都是輸入值加上前面的所有元素之和，之後輸出時只要計算 list[b] - list[a-1] 就能得到 list[a] ~ list[b] 的和了。
本題不做輸入優化也可以。
完整程式碼
AC (33ms, 2.6MB)
#include <stdio.h>
#define BUFSIZ 1048576
long long list[200010];
inline char readChar()
{
static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
if (now == end)
{
if (end < buffer + BUFSIZ)
return EOF;
end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
now = buffer;
}
return *now++;
}
char readInt(int* dst)
{
register char ch;
while ((ch = readChar()) < '-')
if (ch == EOF) return 0;
if (ch == '-')
{
*dst = readChar() ^ '0';
while ((ch = readChar()) >= '0')
* dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
*dst = ~*dst + 1;
}
else
{
*dst = ch ^ '0';
while ((ch = readChar()) >= '0')
* dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
}
return 1;
}
inline void putLongLong(register long long src, const char suffix)
{
register unsigned long long div;
char buffer[22], * st = buffer + 20;
*st = suffix, * (st + 1) = 0;
if (src < 0)
{
src = ~src + 1;
*(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
while (src = div)
* (--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
*(--st) = '-';
}
else
{
do
{
*(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
} while (src = div);
}
fputs(st, stdout);
}
int main()
{
int n, f, t;
readInt(&n);
for (int i = 1; i <= n; i++)
readInt(&t), list[i] = list[i - 1] + t;
readInt(&n);
while (n--)
{
readInt(&f), readInt(&t);
putLongLong(list[t] - list[f - 1], '\n');
}
return 0;
}
|
