10999, Platinum 4

10999, Platinum 4

#include < bits / stdc + + .h >

#define endl "

"

#define ooop(i, n) for ( int i = 0 ; i < n; i + + )

#define loop(i, n) for ( int i = 1 ; i < = n; i + + )

using namespace std ;

typedef long long ll;

typedef pair < int , int > pii;

typedef pair < ll, ll > pll;

const int N = 1e6 ;

ll arr[N + 1 ];

ll seg_tree[ 4 * N];

ll lazy[ 4 * N];

int n, m, k;

void propagate( int seg_i, int arr_l, int arr_r)

{

if (lazy[seg_i]){

seg_tree[seg_i] + = (arr_r - arr_l + 1 ) * lazy[seg_i];

if (arr_l ! = arr_r){

lazy[ 2 * seg_i] + = lazy[seg_i];

lazy[ 2 * seg_i + 1 ] + = lazy[seg_i];

}

lazy[seg_i] = 0 ;

}

}

ll init( int seg_i = 1 , int arr_l = 1 , int arr_r = n)

{

if (arr_l = = arr_r) return seg_tree[seg_i] = arr[arr_r];

int arr_m = (arr_l + arr_r) / 2 ;

return seg_tree[seg_i] = init( 2 * seg_i, arr_l, arr_m) + init( 2 * seg_i + 1 , arr_m + 1 , arr_r);

}

void update( int want_l, int want_r, ll delta, int seg_i = 1 , int arr_l = 1 , int arr_r = n)

{

propagate(seg_i, arr_l, arr_r);

if (arr_r < want_l | | want_r < arr_l) return ;

if (want_l < = arr_l & & arr_r < = want_r){

lazy[seg_i] + = delta;

propagate(seg_i, arr_l, arr_r);

return ;

}

int arr_m = (arr_l + arr_r) / 2 ;

update(want_l, want_r, delta, 2 * seg_i, arr_l, arr_m);

update(want_l, want_r, delta, 2 * seg_i + 1 , arr_m + 1 , arr_r);

seg_tree[seg_i] = seg_tree[ 2 * seg_i] + seg_tree[ 2 * seg_i + 1 ];

}

ll sum_query( int want_l, int want_r, int seg_i = 1 , int arr_l = 1 , int arr_r = n)

{

propagate(seg_i, arr_l, arr_r);

if (want_r < arr_l | | arr_r < want_l) return 0 ;

if (want_l < = arr_l & & arr_r < = want_r) return seg_tree[seg_i];

int arr_m = (arr_l + arr_r) / 2 ;

return sum_query(want_l, want_r, 2 * seg_i, arr_l, arr_m) + sum_query(want_l, want_r, 2 * seg_i + 1 , arr_m + 1 , arr_r);

}

int main()

{

ios::sync_with_stdio( false );

cin .tie( 0 ), cout .tie( 0 );

cin > > n > > m > > k;

loop(i, n) cin > > arr[i];

init();

m + = k;

int a, b, c;

ll d;

while (m - - ){

cin > > a > > b > > c;

if (a = = 1 ){

cin > > d;

update(b, c, d);

}

else cout < < sum_query(b, c) < < endl ;

loop(i, 9 ) cout < < seg_tree[i] < < ' ' ;

cout < < endl ;

loop(i, 9 ) cout < < lazy[i] < < ' ' ;

cout < < endl ;

}

from http://tinycaterpillar.tistory.com/85 by ccl(A) rewrite - 2021-10-08 04:27:02