Grag和Array[差分序列]

题意:

有数列a[ ]; 操作op[ ] = { l, r, d }; 询问q[ ] = { x, y };

操作表示对a的[ l, r ] 区间上每个数增加d; 询问表示执行[ x, y ]之间的op.

打印最终数列.

思路:

用两次差分数列, 先处理出对于每个op调用了几次, 再对数列执行操作.

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 1e5+5; typedef long long ll; ll a[MAXN],sum[MAXN]; ll d[MAXN],delta[MAXN]; int l[MAXN],r[MAXN]; int main() { int n,m,k; scanf('%d %d %d',&n,&m,&k); for(int i=1;i<=n;i++) scanf('%I64d',a+i); for(int i=1;i<=m;i++) scanf('%d %d %I64d',l+i,r+i,delta+i); int x,y; while(k--) { scanf('%d %d',&x,&y); d[x]++;d[y+1]--; } for(int i=1;i<=m;i++) { sum[i] = sum[i-1] + d[i]; delta[i] *= sum[i]; } memset(d,0,sizeof(d)); memset(sum,0,sizeof(sum)); for(int i=1;i<=m;i++) { if(!delta[i]) continue; d[l[i]] += delta[i]; d[r[i]+1] -= delta[i]; } for(int i=1;i<=n;i++) { sum[i] = sum[i-1] + d[i]; a[i] += sum[i]; printf('%I64d%c',a[i],i==n?' ':' '); } }