C++

C++ – N-A135 前缀和

_Redstone_c_

题目链接：https://ac.nowcoder.com/acm/contest/135/I?&headNav=acm

题目描述

Apojacsleam喜欢数组。

他现在有一个n个元素的数组a，而他要对a[L]-a[R]进行M次操作：

  • 操作一：将a[L]-a[R]内的元素都加上P
  • 操作二：将a[L]-a[R]内的元素都减去P

最后询问a[l]-a[r]内的元素之和

输入描述

  • 输入共M+3行：
  • 第一行两个数，n，M，意义如“题目描述”
  • 第二行n个数，描述数组。
  • 第3-M+2行，共M行，每行四个数，q，L，R，P，若q为1表示操作2
  • 第4行，两个正整数l，r

输出描述

  • 一个正整数，为a[l]-a[r]内的元素之和

示例1

输入

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5 5
1 2 3 6
0 2 5 5
0 2 5 8
1 4 9 6
2 7

输出

23

说明

1

题解

前缀和，原数据和修改记录分开保存，到最后好处理。

#include <cstdio>
using namespace std;
const int MAXN = 1e6 + 100;
int n, m;
long long ab[MAXN];        //保存原数据
long long arr[MAXN];       //保存修改记录
int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &ab[i]);       //读入原数据
    for(int i = 0; i < m; i++) {
        long long q, l, r, p;
        scanf("%lld %lld %lld %lld", &q, &l, &r, &p);
        if(q == 1) {
            arr[l] -= p;      //读入修改
            arr[r + 1] += p;
        } else {
            arr[l] += p;
            arr[r + 1] -= p;
        }
    }
    int l, r;
    long long add = 0;
    long long sum = 0;
    scanf("%d %d", &l, &r);
    for(int i = 1 ; i <= r ; i++) {
        add += arr[i];             //前缀和取出当前修改记录值
        if(i >= l && i <= r)sum += add + ab[i];   //如果在区间内，加入答案
    }
    printf("%lld\n", sum);
    return 0;
}

发表回复