CFR 179 1A. Greg and Array ( BIT )
Problem - A - Codeforces
二回べつべつに区間操作するのは自明。まずどの操作が何回使われるかを統計して終えてから操作毎に区間addをすればいい。
Range add と Single query しかないので BITの方がかなり楽。
追記:いや、普通にarrayの上でいもすすればいいじゃんOAO
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXM = 1e5 + 5; const int MAXK = 1e5 + 5; typedef long long ll; int n, m, k; int a[ MAXN ]; int opl[ MAXM ], opr[ MAXM ], opd[ MAXM ]; int x[ MAXK ], y[ MAXK ]; struct BIT{ vector< ll > dat; int sz; void init( int _n ){ sz = _n; dat.resize( _n + 1 ); fill( dat.begin(), dat.end(), 0 ); } void add( int k, ll val ){ for( int i = k; i <= sz; i += i & -i ) dat[ i ] += val; } ll sum( int k ){ ll res = 0; for( int i = k; i > 0; i -= i & -i ) res += dat[ i ]; return res; } }; void solve(){ BIT op; op.init( m + 1 ); for( int i = 1; i <= k; ++i ) op.add( x[ i ], 1 ), op.add( y[ i ] + 1, -1 ); BIT na; na.init( n + 1 ); for( int i = 1; i <= m; ++i ){ ll d = op.sum( i ) * opd[ i ]; na.add( opl[ i ], d ); na.add( opr[ i ] + 1, -d ); } for( int i = 1; i <= n; ++i ) cout << na.sum( i ) + a[ i ] << ( i == n ? '\n' : ' ' ); } int main(){ ios::sync_with_stdio( false ); cin >> n >> m >> k; for( int i = 1; i <= n; ++i ) cin >> a[ i ]; for( int i = 1; i <= m; ++i ) cin >> opl[ i ] >> opr[ i ] >> opd[ i ]; for( int i = 1; i <= k; ++i ) cin >> x[ i ] >> y[ i ]; solve(); return 0; }