Greg and Array CodeForces - 296C

给定一个数列 \(a= { a_1,a_2,...,a_n }\) 以及 \(m\) 次操作，\(q\) 次查询。

其中第 \(i\) 次操作如同：\(l_i, r_i, d_i\)，意指区间 \([ l_i, r_i]\) 中每个元素加上 \(d_i\)。

其中第 \(i\) 次查询如同：\(x_i, y_i\)，意指需要执行第 \(x_i,x_i+1,...y_i\) 次操作。

现在问你，执行完所有查询后的序列 \(a\) 是怎么样的。

Input

第 \(1\) 行 \(n,m,k\)；

第 \(2\) 行 \(a_1,a_2,...,a_n\)；

接下来 \(m\) 行，每行三个整数 \(l_i,r_i,d_i\)；

接下来 \(k\) 行，每行三个整数 \(x_i,y_i\)；

数据范围：\(1≤n,m,k≤10^5, 1≤l_i≤r_i≤n, 0≤a_i,d_i≤10^5, 1≤x_i≤y_i≤m\)。

Output

单行打印 \(a_1, a_2, ..., a_n\)。用空格分隔打印的数字。

Sample Input 1

Sample Output 1

9 18 17

分析

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e6+10,INF=0x3f3f3f3f;

LL n,m,k,a[N],l[N],r[N],d[N],res=0;

LL b[N],c[N];

//#define local

int main(){

#ifdef local

    freopen("data.in", "r", stdin);

//    freopen("data.out", "w", stdout);

#endif

    cin>>n>>m>>k;

    for(int i=1; i<=n; i++) cin>>a[i];

    for(int i=1; i<=m; i++) cin>>l[i]>>r[i]>>d[i];

    int x,y;

    while(k--){

        cin>>x>>y; b[x]++, b[y+1]--;

    }

    for(int i=1; i<=m; i++) b[i]+=b[i-1];

    for(int i=1; i<=m; i++){

        c[l[i]] += d[i]*b[i];

        c[r[i]+1] -= d[i]*b[i];

    }

    for(int i=1; i<=n; i++) c[i]+=c[i-1], a[i]+=c[i];

    for(int i=1; i<=n; i++) cout<<a[i]<<" \n"[i==n];

    return 0;

}

巴特西

Greg and Array CodeForces - 296C - 差分

Input

Output

Sample Input 1

Sample Output 1

分析

最新文章

热门文章