Submit Info #18389

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

ケース詳細
Name Status Time Memory
example_00 AC 20 ms 37.30 MiB
max_random_00 AC 242 ms 39.73 MiB
max_random_01 AC 245 ms 39.50 MiB
max_random_02 AC 242 ms 39.75 MiB
medium_00 AC 20 ms 37.30 MiB
medium_01 AC 21 ms 37.35 MiB
medium_02 AC 22 ms 37.40 MiB
random_00 AC 175 ms 39.00 MiB
random_01 AC 183 ms 39.14 MiB
random_02 AC 124 ms 38.27 MiB
small_00 AC 19 ms 37.34 MiB
small_01 AC 20 ms 37.30 MiB
small_02 AC 21 ms 37.37 MiB
small_03 AC 21 ms 37.35 MiB
small_04 AC 19 ms 37.28 MiB
small_05 AC 21 ms 37.29 MiB
small_06 AC 20 ms 37.29 MiB
small_07 AC 18 ms 37.31 MiB
small_08 AC 19 ms 37.32 MiB
small_09 AC 20 ms 37.30 MiB

// RANGE CHMIN CHMAX ADD RANGE SUM // https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum #include <iostream> using namespace std; typedef int64_t LI; typedef unsigned UI; typedef pair<UI,LI> Pair; const UI MaxN = 200005; class SegmentTree { public: #define lKid rt << 1 #define rKid rt << 1 | 1 const Pair OK = Pair( 1, 0 ); struct STNode { LI s; LI mn; LI mx; UI len; STNode( LI a = 0, LI b = 0, LI c = 0, UI d = 0 ) { s = a; mn = b; mx = c; len = d; } }; // --MEMBERS STNode T[MaxN<<2]; // MAIN TREE Pair lzy[MaxN<<2]; // AFFINE LAZY UPDATE TREE LI a[MaxN]; // --METHODS void build( UI rt, UI L, UI R ) { T[rt].len = R - L + 1; if( L == R ) { T[rt].mn = T[rt].mx = T[rt].s = a[L]; return; } UI mid = ( L + R ) >> 1; build( lKid, L, mid ); build( rKid, mid + 1, R ); lzy[rt] = OK; combineKids( rt ); } void update( UI rt, UI L, UI R, UI x, UI y, const Pair& v ) { if( y < L || R < x ) return; if( L >= x && R <= y ) { merge( rt, v ); return; } propagate( rt ); UI mid = ( L + R ) >> 1; update( lKid, L, mid, x, y, v ); update( rKid, mid + 1, R, x, y, v ); combineKids( rt ); } void minUpdate( UI rt, UI L, UI R, UI x, UI y, LI v ) { if( y < L || R < x || T[rt].mx <= v ) return; if( L >= x && R <= y && v <= T[rt].mn ) { Pair p( 0, v ); merge( rt, p ); return; } propagate( rt ); UI mid = ( L + R ) >> 1; minUpdate( lKid, L, mid, x, y, v ); minUpdate( rKid, mid + 1, R, x, y, v ); combineKids( rt ); } void maxUpdate( UI rt, UI L, UI R, UI x, UI y, LI v ) { if( y < L || R < x || T[rt].mn >= v ) return; if( L >= x && R <= y && v >= T[rt].mx ) { Pair p( 0, v ); merge( rt, p ); return; } propagate( rt ); UI mid = ( L + R ) >> 1; maxUpdate( lKid, L, mid, x, y, v ); maxUpdate( rKid, mid + 1, R, x, y, v ); combineKids( rt ); } LI query( UI rt, UI L, UI R, UI x, UI y ) { if( L >= x && R <= y ) return T[rt].s; propagate( rt ); UI mid = ( L + R ) >> 1; if( y <= mid ) return query( lKid, L, mid, x, y ); if( x > mid ) return query( rKid, mid + 1, R, x, y ); return add( query( lKid, L, mid, x, y ), query( rKid, mid + 1, R, x, y ) ); } private: LI add( LI x, LI y ) { return x + y; } void combineKids( UI rt ) { T[rt].s = add( T[lKid].s, T[rKid].s ); T[rt].mn = min( T[lKid].mn, T[rKid].mn ); T[rt].mx = max( T[lKid].mx, T[rKid].mx ); } void merge( UI rt, const Pair& v ) { LI b = v.second; if( v.first ) { T[rt].s += T[rt].len * b; T[rt].mn += b; T[rt].mx += b; lzy[rt].second += b; } else { T[rt].s = T[rt].len * b; lzy[rt].first = 0; T[rt].mn = T[rt].mx = lzy[rt].second = b; } } void propagate( UI rt ) { if( lzy[rt] == OK ) return; merge( lKid, lzy[rt] ); merge( rKid, lzy[rt] ); lzy[rt] = OK; } }; SegmentTree tree; int main() { ios::sync_with_stdio( 0 ); cin.tie( 0 ); cout.tie( 0 ); UI n, q; cin >> n >> q; for( UI i=1 ; i<=n ; ++i ) cin >> tree.a[i]; tree.build( 1, 1, n ); while( q-- ) { UI typ, L, R; LI v; cin >> typ >> L >> R; ++L; if( typ == 0 ) { cin >> v; tree.minUpdate( 1, 1, n, L, R, v ); } else if( typ == 1 ) { cin >> v; tree.maxUpdate( 1, 1, n, L, R, v ); } else if( typ == 2 ) { Pair v( 1, 0 ); cin >> v.second; tree.update( 1, 1, n, L, R, v ); } else cout << tree.query( 1, 1, n, L, R ) << '\n'; } return 0; }