[CF 295A]Grag and 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?'\n':' ');
    }
}