算法思路
1.读取输入,包括序列长度、操作次数以及原始序列。
2.将原始序列的每个位置视为一个区间,对每个区间进行一次增加操作,将增量保存在一个新的数组中。
3.执行每个操作,读取操作的范围和增加的值,将增量记录在新的数组中,保证增量的影响范围正确。
4.对新数组进行前缀和运算,得到最终的序列。
C++ 代码
#include<iostream>
using namespace std;
const int N=100010; // 定义序列长度的最大值
int n,m; // 序列长度和操作次数
int a[N],b[N]; // 原始序列以及操作后的序列
void insert(int l,int r,int c)
{
// 将序列中 [l,r] 区间的每个数加上 c
b[l] += c; // 在区间左端点增加 c
b[r+1] -= c; // 在区间右端点后一个位置减去 c,保证影响的范围正确
}
int main()
{
scanf("%d%d",&n,&m); // 输入序列长度和操作次数
for(int i=1;i<=n;i++) //从1开始是为了方便处理边界情况
scanf("%d",&a[i]); // 输入原始序列
// 对原始序列进行处理,即对每个位置应用一次操作
for(int i=1;i<=n;i++)
insert(i,i,a[i]); //对原始序列 a 中的每个元素应用一次操作,并将操作结果存储在增量数组 b 中
//在增量数组 b[] 中记录下所有对原始序列 a[] 的操作,然后通过对增量数组求前缀和,最终得到最终的序列
// 执行每个操作
while(m--)
{
int l,r,c;
scanf("%d%d%d",&l,&r,&c); // 输入操作的范围和增加的值
insert(l,r,c); // 执行操作
}
// 计算最终序列
for(int i=1;i<=n;i++)
b[i] += b[i-1]; // 将当前位置 i 的值加上前一个位置 i-1 的值。b[i] 存储的是增量值,是对原始序列进行操作后的累加值
// 输出最终序列
for(int i=1;i<=n;i++)
printf("%d ",b[i]);
return 0;
}