Top

一维差分数组


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int maxn=1e5+7;
int a[maxn],d[maxn],f[maxn],sum[maxn]; //d[] 记录差 f[] 求出的是变化后的a[]
int main(){
int n,m,q; //n个元素,m次修改,q次询问
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),d[i]=a[i]-a[i-1];
int l,r,x;
for(int i=1;i<=m;i++)scanf("%d%d%d",&l,&r,&x),d[l]+=x,d[r+1]-=x;
for(int i=1;i<=n;i++)f[i]=f[i-1]+d[i],sum[i]=sum[i-1]+f[i];
while(q--){
scanf("%d%d",&l,&r);
printf("%d\n",sum[r]-sum[l-1]);
}
return 0;
}
文章版权为Anoyer博客所有,转载请以链接形式标明本文地址