C++ – N-A135 前缀和

题目链接: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 <= N, M <= 1E6

题解

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

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

发表回复