1 条题解
-
1チルノ (9Cirno) LV 7 MOD Baka tayz @ 2024-04-18 19:01:27
本题实际上是对于 \(m\) 个询问 \(l_i, r_i\),求 \([l_i, r_i]\) 区间和。
最直接的思路是对于每次询问,从 \(l_i\) 枚举至 \(r_i\),并将每个位置上的数加起来,这样复杂度是 \(O(n \times m)\) 的,可以通过 \(50\%\) 的数据。
设 \(sum_i\) 表示第 \(1\) 个数到第 \(i\) 个数的和,及 \(sum_i = \sum^{n}_{i = 1} a_i = a_1 + a_2 + \dots +a_n\),记 \(s_0 = 0\),这里 \(s\) 数组记录的数值,成为 前缀和,也就是对每个前缀区间求和。
那么很显然,对于询问 \(l_i\) 到 \(r_i\) 之间的和就等价于 \(sum_{r_i} - sum_{l_i - 1} = (a_1 - a_1) + (a_2 - a_2) + \dots + (a_{l_i - 1} - a_{l_i - 1}) + a_{l_i} + a_{l_i + 1} + \dots + a_{r_i}\),求出 \(s\) 数值后,即可求出任意区间的区间。
代码如下:
#include <cstdio> #define ll long long #define MAXN 100010 int n, m; ll a[MAXN]; ll sum[MAXN]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), sum[i] = sum[i - 1] + a[i]; scanf("%d", &m); for (int i = 1; i <= m; i++) { int l, r; scanf("%d %d", &l, &r); printf("%lld\n", sum[r] - sum[l - 1]); } return 0; }
- 1