思路:
对于一个数组。在[l,r]上都加c,会超时。
(个人认为的)差分思想:在一个数组num[]上,将num[i]的值分散到这个数和前面那个数上,即为num[i]=num[i-1]+dif[i];
定义一个新数组dif[],让dif[i]=num[i]-num[i-1];这个数组表示原数组第i个数的值和第i-个数组的值的和。
执行[l,r]都加c的操作时,只需要对l位置上的差分数组加c,这样在回复成原数组时,
num[l]等于num[l-1]+dif[l],此时dif[l]已经加上c了,所以num[l]会比原来大c。
由于每一项num[i]的值都会加上num[i-1]。以此l位置以后的都会比原来大c。
因为+c操作到r结束,因此要执行dif[r+1]-c操作,保证r以后的数在+c后再把c剪掉。保持不变
如图
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int num[N],dif[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>num[i];
dif[i]=num[i]-num[i-1];
}
int l,r,c;
for(int i=0;i<m;i++){
cin>>l>>r>>c;
dif[l]+=c;
dif[r+1]-=c;
}
for(int i=1;i<=n;i++){
num[i]=dif[i]+num[i-1];
cout<<num[i]<<" ";
}
cout<<endl;
return 0;
}