差分 10.29
#include <iostream>
using namespace std;
const int N=100010;
int a[N],b[N];
int l,r,c,n,m;
void ins(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
int main(){
cin>>n>>m;
for(int i=1;i<n+1;i++)cin>>a[i];
for(int i=1;i<n+1;i++)ins(i,i,a[i]);
for(int i=1;i<m+1;i++){
cin>>l>>r>>c;
ins(l,r,c);
}
for(int i=1;i<n+1;i++){
a[i]=b[i]+a[i-1];
}
for(int i=1;i<n+1;i++)cout<<a[i]<<" ";
}
本次代码学习的是差分,本质上是前缀和的逆运算----把b[0]到b[i]项目加起来,正好能得到a[i],我们便可以说b是a的差分数组。
在本题中,我们要处理的事情是:当用户输入l,r,c三个数字时,我们把a数组中[l,r]的所有数字都加上c,比较容易考虑的方式是直接到a数组中从l遍历到r把每一项都加上c,但这样做每次用户操作的时候我们都需要不断的遍历a数组,于是我们想到了差分–创造一个差分数组b,然后把a的所有抽象层面的操作移动到b上完成,最后用b来重新创造a。
当我们操作b的时候,就只需要移动到l去加上c和r+1去减去c(因为r本身也要加上c),这样,在未来重新算前缀和的时候,我们就能把历次的操作一次性运算到位,至此全题ac