[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);
    forint i=1;i<=n;i++)
        scanf"%I64d",a+i);
    forint i=1;i<=m;i++)
        scanf"%d %d %I64d",l+i,r+i,delta+i);
    int x,y;
    whilek--)
    {
        scanf"%d %d",&x,&y);
        d[x]++;d[y+1]--;
    }
    forint i=1;i<=m;i++)
    {
        sum[i] = sum[i-1] + d[i];
        delta[i] *= sum[i];
    }
    memsetd,0,sizeofd));
    memsetsum,0,sizeofsum));
    forint i=1;i<=m;i++)
    {
        if!delta[i])    continue;
        d[l[i]] += delta[i];
        d[r[i]+1] -= delta[i];
    }
    forint i=1;i<=n;i++)
    {
        sum[i] = sum[i-1] + d[i];
        a[i] += sum[i];
        printf"%I64d%c",a[i],i==n?'
':' ');
    }
}