Submit Info #17202

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

ケース詳細
Name Status Time Memory
example_00 AC 20 ms 37.30 MiB
max_random_00 AC 253 ms 39.80 MiB
max_random_01 AC 258 ms 39.82 MiB
max_random_02 AC 253 ms 39.70 MiB
medium_00 AC 21 ms 37.38 MiB
medium_01 AC 22 ms 37.36 MiB
medium_02 AC 20 ms 37.30 MiB
random_00 AC 172 ms 38.96 MiB
random_01 AC 190 ms 39.17 MiB
random_02 AC 128 ms 38.29 MiB
small_00 AC 22 ms 37.33 MiB
small_01 AC 23 ms 37.31 MiB
small_02 AC 21 ms 37.29 MiB
small_03 AC 19 ms 37.30 MiB
small_04 AC 20 ms 37.30 MiB
small_05 AC 21 ms 37.36 MiB
small_06 AC 21 ms 37.30 MiB
small_07 AC 24 ms 37.02 MiB
small_08 AC 20 ms 37.41 MiB
small_09 AC 22 ms 37.09 MiB

// RANGE CHMIN CHMAX ADD RANGE SUM // https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum // PASSED ALL Library-Checker TESTS #include <iostream> using namespace std; typedef int64_t LI; typedef pair<LI,LI> Pair; const int 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; LI len; STNode( LI a = 0, LI b = 0, LI c = 0, LI d = 0 ) { s = a; mn = b; mx = c; len = d; } }; private: // --MEMBERS STNode T[MaxN<<2]; // MAIN TREE Pair lzy[MaxN<<2]; // AFFINE LAZY UPDATE TREE public: LI a[MaxN]; // --METHODS void build( int rt, int L, int R ) { T[rt].len = R - L + 1; if( L == R ) { T[rt].mn = T[rt].mx = T[rt].s = a[L]; return; } int mid = ( L + R ) >> 1; build( lKid, L, mid ); build( rKid, mid + 1, R ); lzy[rt] = OK; combineKids( rt ); } void update( int rt, int L, int R, int x, int y, Pair v ) { if( y < L || R < x ) return; if( L >= x && R <= y ) { merge( rt, v ); return; } propagate( rt ); int mid = ( L + R ) >> 1; update( lKid, L, mid, x, y, v ); update( rKid, mid + 1, R, x, y, v ); combineKids( rt ); } void minUpdate( int rt, int L, int R, int x, int y, LI v ) { if( y < L || R < x || T[rt].mx <= v ) return; if( L >= x && R <= y && v <= T[rt].mn ) { merge( rt, Pair( 0, v ) ); return; } propagate( rt ); int mid = ( L + R ) >> 1; minUpdate( lKid, L, mid, x, y, v ); minUpdate( rKid, mid + 1, R, x, y, v ); combineKids( rt ); } void maxUpdate( int rt, int L, int R, int x, int y, LI v ) { if( y < L || R < x || T[rt].mn >= v ) return; if( L >= x && R <= y && v >= T[rt].mx ) { merge( rt, Pair( 0, v ) ); return; } propagate( rt ); int mid = ( L + R ) >> 1; maxUpdate( lKid, L, mid, x, y, v ); maxUpdate( rKid, mid + 1, R, x, y, v ); combineKids( rt ); } LI query( int rt, int L, int R, int x, int y ) { if( y < L || R < x ) return LI( 0 ); if( L >= x && R <= y ) return T[rt].s; propagate( rt ); int mid = ( L + R ) >> 1; 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( int 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( int rt, 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( int 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 ); int n, q; cin >> n >> q; for( int i=1 ; i<=n ; ++i ) cin >> tree.a[i]; tree.build( 1, 1, n ); while( q-- ) { int 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 ) { cin >> v; tree.update( 1, 1, n, L, R, Pair( 1, v ) ); } else cout << tree.query( 1, 1, n, L, R ) << '\n'; } return 0; }