Week5 作业 B

题目描述：

给定一个长度为n的序列A，要求支持操作ADD(L,R,x)表示对A[L]~A[R]的每个数都加上x。问最后序列A是什么样的。

思路：

用差分数组实现区间操作，最后差分数组的前缀和SUM[i]就是A[i]

具体的，设差分数组为B，则对A[L]~A[R]的每个数都加上x，等价于，对B[L]+x 和对B[R+1]-x

代码：

 1 #include <cstdio>
 2 #include <iostream>
 3 using namespace std;
 4 const int MAXN=1e6+5;
 5 long long a[MAXN],b[MAXN],sum[MAXN];
 6 int main()
 7 {
 8     int n,q; cin>>n>>q;
 9     for(int i=1;i<=n;i++)
10         scanf("%lld",a+i);
11     for(int i=1;i<=n;i++)
12         b[i]=a[i]-a[i-1];
13     int l,r,c;
14     for(int i=1;i<=q;i++)
15     {
16         scanf("%d %d %d",&l,&r,&c);
17         b[l]+=c;
18         b[r+1]-=c;
19     }
20     for(int i=1;i<=n;i++)
21         sum[i]=sum[i-1]+b[i];
22     for(int i=1;i<=n;i++)
23         printf( (i==1) ? "%lld" :" %lld",sum[i]);
24     return 0;
25 }