C++

C++ – N-A135 prefix sum

_Redstone_c_

Question link:https://ac.nowcoder.com/acm/contest/135/I?&headNav=acm

Question description

Apojacsleam loves arrays.

He now has an array a of n elements, and he wants to perform M operations on a[L]-a[R]:

  • Operation 1: Add P to all the elements in a[L]-a[R]
  • Operation 2: Subtract P from all elements in a[L]-a[R]

Finally, ask the sum of the elements in a[l]-a[r]

Enter description

  • Enter a total of M+3 lines:
  • The first line of the two numbers, n, M, means "problem description"
  • The second line contains n numbers, describing the array.
  • Line 3-M+2, M lines in total, each line has four numbers, q, L, R, P. If q is 1, it means operation 2
  • Line 4, two positive integers l, r

Output description

  • A positive integer, which is the sum of the elements in a[l]-a[r]

Example 1

enter

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

Output

23

Description

1

answer

Prefix sum, original data and modification records are saved separately to facilitate processing at the end.

#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;
}

Post Reply