1 条题解

  • 1
    @ 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

信息

ID
1005
难度
9
分类
模拟 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者