Submit Info #17112

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp harrybehemoth AC 347 ms 23.77 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 6.80 MiB
max_random_00 AC 342 ms 23.75 MiB
max_random_01 AC 347 ms 23.77 MiB
max_random_02 AC 341 ms 23.67 MiB
medium_00 AC 6 ms 6.92 MiB
medium_01 AC 7 ms 6.80 MiB
medium_02 AC 7 ms 6.80 MiB
random_00 AC 228 ms 15.42 MiB
random_01 AC 249 ms 23.42 MiB
random_02 AC 144 ms 11.37 MiB
small_00 AC 4 ms 6.80 MiB
small_01 AC 6 ms 6.80 MiB
small_02 AC 6 ms 6.84 MiB
small_03 AC 5 ms 6.80 MiB
small_04 AC 0 ms 6.80 MiB
small_05 AC 1 ms 6.80 MiB
small_06 AC 0 ms 6.74 MiB
small_07 AC 4 ms 6.80 MiB
small_08 AC 7 ms 6.80 MiB
small_09 AC 1 ms 6.74 MiB

#include <bits/stdc++.h> using namespace std; typedef int64_t LI; const int MAXN = 200005; #define lKid rt << 1 #define rKid rt << 1 | 1 LI mn[MAXN << 2]; LI mx[MAXN << 2]; LI s[MAXN << 2]; LI a[MAXN << 2]; LI b[MAXN << 2]; void propagate( int rt, int L, int R ) { LI A = a[rt]; LI B = b[rt]; if( A == 1 && B == 0 ) return; mn[rt] = mn[rt] * A + B; mx[rt] = mx[rt] * A + B; s[rt] = s[rt] * A + ( R - L + 1 ) * B; if( L < R ) { a[lKid] = a[lKid] * A; b[lKid] = b[lKid] * A + B; a[rKid] = a[rKid] * A; b[rKid] = b[rKid] * A + B; } a[rt] = 1; b[rt] = 0; } void minUpdate( int rt, int L, int R, int l, int r, LI x ) { propagate( rt, L, R ); if( R < l || r < L || mx[rt] <= x ) return; if( l <= L && R <= r && x <= mn[rt] ) { a[rt] = 0; b[rt] = x; propagate( rt, L, R ); return; } int mid = ( L + R ) >> 1; minUpdate( lKid, L, mid, l, r, x ); minUpdate( rKid, mid + 1, R, l, r, x ); s[rt] = s[lKid] + s[rKid]; mn[rt] = min( mn[lKid], mn[rKid] ); mx[rt] = max( mx[lKid], mx[rKid] ); } void maxUpdate( int rt, int L, int R, int l, int r, LI x ) { propagate( rt, L, R ); if( R < l || r < L || mn[rt] >= x ) return; if( l <= L && R <= r && x >= mx[rt] ) { a[rt] = 0; b[rt] = x; propagate( rt, L, R ); return; } int mid = ( L + R ) >> 1; maxUpdate( lKid, L, mid, l, r, x ); maxUpdate( rKid, mid + 1, R, l, r, x ); s[rt] = s[lKid] + s[rKid]; mn[rt] = min( mn[lKid], mn[rKid] ); mx[rt] = max( mx[lKid], mx[rKid] ); } void update( int rt, int L, int R, int l, int r, LI x ) { propagate( rt, L, R ); if( R < l || r < L ) return; if( l <= L && R <= r ) { b[rt] += x; propagate( rt, L, R ); return; } int mid = ( L + R ) >> 1; update( lKid, L, mid, l, r, x ); update( rKid, mid + 1, R, l, r, x ); s[rt] = s[lKid] + s[rKid]; mn[rt] = min( mn[lKid], mn[rKid] ); mx[rt] = max( mx[lKid], mx[rKid] ); } LI get( int rt, int L, int R, int l, int r ) { propagate( rt, L, R ); if( R < l || r < L ) return 0LL; if( l <= L && R <= r ) return s[rt]; int mid = ( L + R ) >> 1; return get( lKid, L, mid, l, r ) + get( rKid, mid + 1, R, l, r ); } int main() { ios::sync_with_stdio( 0 ); cin.tie( 0 ); int n, q; cin >> n >> q; for( int i=0 ; i<(MAXN<<2) ; ++i ) a[i] = 1; LI v = 0; for( int i=1 ; i<=n; ++i ) { cin >> v; update( 1, 1, n, i, i, v ); } while( q-- ) { int typ, l, r; cin >> typ >> l >> r; ++l; if( typ == 0 ) { cin >> v; minUpdate( 1, 1, n, l, r, v ); } else if( typ == 1 ) { cin >> v; maxUpdate( 1, 1, n, l, r, v ); } else if( typ == 2 ) { cin >> v; update( 1, 1, n, l, r, v ); } else cout << get( 1, 1, n, l, r ) << "\n"; } return 0; }