# 题目

题目:

输入一个长度为 n 的整数序列。
接下来输入 m 个操作,每个操作包含三个整数 l, r, c,表示将序列中 [l, r] 之间的每个数加上 c。
请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 n 和 m。
第二行包含 n 个整数,表示整数序列。
接下来 m 行,每行包含三个整数 l,r,c,表示一个操作。

输出格式

共一行,包含 n 个整数,表示最终序列。

# 思路

对一个区间内的数加 C,如果暴力加,会浪费很多时间,我们可以开一个新数组用于差分操作,数组下标就代表数轴上的每一个数,每次给定一个区间,把以区间左端点未下标的数组值加上 C,而以(区间右端点 + 1)为下标的数组值减去 C,进行 m 次操作后,再求一次前缀和并加上原来数组的值就是进行区间操作后的数组,参考下图:

# Code

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[100],b[100];  //例题,开的很小,你可以开大
int main()
{
//	freopen("test.txt","r",stdin); 
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
//		b[i]+=a[i];
//		b[i+1]-=a[i];  //也可以初始化b数组就加上a数组的值,如果这样做了,下面就不能加a数组的值了
	}
	for(int i=1;i<=m;i++){
		int l,r,c;
		cin>>l>>r>>c;
		b[l]+=c;
		b[r+1]-=c;
	}
	for(int i=1;i<=n;i++) b[i]+=b[i-1]; //前缀和
	for(int i=1;i<=n;i++) cout<<b[i]+a[i]<<" ";  //一定要记得加上原数组的值
}

复杂度: O (N),小于 1e8 的数据量都可以过

很简单的算法吧(owo)

更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝