Submit Info #22247

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp Mehedi AC 232 ms 39.80 MiB

ケース詳細
Name Status Time Memory
example_00 AC 20 ms 37.30 MiB
max_random_00 AC 231 ms 39.75 MiB
max_random_01 AC 232 ms 39.78 MiB
max_random_02 AC 227 ms 39.80 MiB
medium_00 AC 20 ms 37.30 MiB
medium_01 AC 22 ms 37.36 MiB
medium_02 AC 21 ms 37.30 MiB
random_00 AC 162 ms 38.92 MiB
random_01 AC 172 ms 39.17 MiB
random_02 AC 117 ms 38.30 MiB
small_00 AC 20 ms 37.30 MiB
small_01 AC 21 ms 37.30 MiB
small_02 AC 22 ms 37.30 MiB
small_03 AC 20 ms 37.37 MiB
small_04 AC 20 ms 37.30 MiB
small_05 AC 21 ms 37.31 MiB
small_06 AC 19 ms 37.31 MiB
small_07 AC 19 ms 37.30 MiB
small_08 AC 21 ms 37.30 MiB
small_09 AC 20 ms 37.39 MiB

#include <iostream> using namespace std; typedef int64_t ll; //typedef unsigned ll; typedef pair<ll, ll> pii; const ll MaxN = 200005; class SegmentTree { public: #define lKid rt << 1 #define rKid rt << 1 | 1 const pii OK = pii( 1, 0 ); struct STNode { ll s; ll mn; ll mx; ll len; STNode( ll a = 0, ll b = 0, ll c = 0, ll d = 0 ) { s = a; mn = b; mx = c; len = d; } }; // --MEMBERS STNode T[MaxN << 2]; // MAIN Tree pii lzy[MaxN << 2]; // AFFINE LAZY UPDATE Tree ll a[MaxN]; // --METHODS void build( ll rt, ll L, ll R ) { T[rt].len = R - L + 1; if ( L == R ) { T[rt].mn = T[rt].mx = T[rt].s = a[L]; return; } ll mid = ( L + R ) >> 1; build( lKid, L, mid ); build( rKid, mid + 1, R ); lzy[rt] = OK; combineKids( rt ); } void update( ll rt, ll L, ll R, ll x, ll y, const pii& v ) { if ( y < L || R < x ) return; if ( L >= x && R <= y ) { merge( rt, v ); return; } propagate( rt ); ll mid = ( L + R ) >> 1; update( lKid, L, mid, x, y, v ); update( rKid, mid + 1, R, x, y, v ); combineKids( rt ); } void minUpdate( ll rt, ll L, ll R, ll x, ll y, ll v ) { if ( y < L || R < x || T[rt].mx <= v ) return; if ( L >= x && R <= y && v <= T[rt].mn ) { pii p( 0, v ); merge( rt, p ); return; } propagate( rt ); ll mid = ( L + R ) >> 1; minUpdate( lKid, L, mid, x, y, v ); minUpdate( rKid, mid + 1, R, x, y, v ); combineKids( rt ); } void maxUpdate( ll rt, ll L, ll R, ll x, ll y, ll v ) { if ( y < L || R < x || T[rt].mn >= v ) return; if ( L >= x && R <= y && v >= T[rt].mx ) { pii p( 0, v ); merge( rt, p ); return; } propagate( rt ); ll mid = ( L + R ) >> 1; maxUpdate( lKid, L, mid, x, y, v ); maxUpdate( rKid, mid + 1, R, x, y, v ); combineKids( rt ); } ll Query( ll rt, ll L, ll R, ll x, ll y ) { if ( L >= x && R <= y ) return T[rt].s; propagate( rt ); ll 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: ll add( ll x, ll y ) { return x + y; } void combineKids( ll 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( ll rt, const pii& v ) { ll 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( ll rt ) { if ( lzy[rt] == OK ) return; merge( lKid, lzy[rt] ); merge( rKid, lzy[rt] ); lzy[rt] = OK; } }; SegmentTree Tree; int main() { /* #ifndef ONllNE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif //*/ ios::sync_with_stdio( 0 ); cin.tie( 0 ); cout.tie( 0 ); ll n, q; cin >> n >> q; for ( ll i = 1 ; i <= n ; ++i ) cin >> Tree.a[i]; Tree.build( 1, 1, n ); while ( q-- ) { ll typ, L, R; ll 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 ) { pii 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; }