Submit Info #40890

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp wleungBVG AC 600 ms 50.89 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
max_random_00 AC 491 ms 50.74 MiB
max_random_01 AC 476 ms 50.77 MiB
max_random_02 AC 471 ms 50.79 MiB
medium_00 AC 3 ms 0.80 MiB
medium_01 AC 3 ms 0.66 MiB
medium_02 AC 0 ms 0.62 MiB
random2_00 AC 532 ms 50.88 MiB
random2_01 AC 532 ms 50.89 MiB
random2_02 AC 528 ms 50.86 MiB
random3_00 AC 600 ms 49.86 MiB
random3_01 AC 598 ms 49.92 MiB
random3_02 AC 600 ms 49.95 MiB
random_00 AC 317 ms 27.20 MiB
random_01 AC 341 ms 48.31 MiB
random_02 AC 218 ms 13.68 MiB
small_00 AC 1 ms 0.65 MiB
small_01 AC 3 ms 0.67 MiB
small_02 AC 0 ms 0.68 MiB
small_03 AC 2 ms 0.67 MiB
small_04 AC 2 ms 0.67 MiB
small_05 AC 1 ms 0.67 MiB
small_06 AC 2 ms 0.62 MiB
small_07 AC 2 ms 0.66 MiB
small_08 AC 1 ms 0.66 MiB
small_09 AC 3 ms 0.59 MiB

#include <bits/stdc++.h> using namespace std; template <class C> constexpr int sz(const C &c) { return int(c.size()); } constexpr const char nl = '\n', sp = ' '; using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; #if __SIZEOF_INT128__ using i128 = __int128_t; using ui128 = __uint128_t; #endif template <class C> struct SegmentTreeBeats { using Data = typename C::Data; using Lazy = typename C::Lazy; using Arg = typename C::Arg; struct Node { Data val; Lazy lz; Node() : val(C::qdef()), lz(C::ldef()) {} }; int N; vector<Node> TR; void apply(int x, int tl, int tr, const Lazy &v) { TR[x].val = C::applyLazy(TR[x].val, C::getSegmentVal(v, tr - tl + 1)); TR[x].lz = C::mergeLazy(TR[x].lz, v); } void propagate(int x, int tl, int tr) { if (TR[x].lz != C::ldef()) { int m = tl + (tr - tl) / 2; apply(x * 2, tl, m, TR[x].lz); apply(x * 2 + 1, m + 1, tr, TR[x].lz); TR[x].lz = C::ldef(); } } template <class F> void build(int x, int tl, int tr, F &f) { if (tl == tr) { TR[x].val = f(); return; } int m = tl + (tr - tl) / 2; build(x * 2, tl, m, f); build(x * 2 + 1, m + 1, tr, f); TR[x].val = C::merge(TR[x * 2].val, TR[x * 2 + 1].val); } void update(int x, int tl, int tr, int l, int r, const Arg &v) { if (r < tl || tr < l || C::breakCond(TR[x].val, v)) return; if (l <= tl && tr <= r && C::tagCond(TR[x].val, v)) { Lazy lz = C::makeLazy(TR[x].val, v); TR[x].val = C::applyLazy(TR[x].val, C::getSegmentVal(lz, tr - tl + 1)); TR[x].lz = C::mergeLazy(TR[x].lz, lz); return; } propagate(x, tl, tr); int m = tl + (tr - tl) / 2; update(x * 2, tl, m, l, r, v); update(x * 2 + 1, m + 1, tr, l, r, v); TR[x].val = C::merge(TR[x * 2].val, TR[x * 2 + 1].val); } Data query(int x, int tl, int tr, int l, int r) { if (r < tl || tr < l) return C::qdef(); if (l <= tl && tr <= r) return TR[x].val; propagate(x, tl, tr); int m = tl + (tr - tl) / 2; return C::merge(query(x * 2, tl, m, l, r), query(x * 2 + 1, m + 1, tr, l, r)); } template <class F> int bsearchPrefix(int x, int tl, int tr, int l, int r, Data &agg, F f) { if (r < tl || tr < l) return r + 1; if (tl != tr) propagate(x, tl, tr); if (l <= tl && tr <= r) { Data v = C::merge(agg, TR[x].val); if (!f(v)) { agg = v; return r + 1; } } if (tl == tr) return tl; int m = tl + (tr - tl) / 2; int ret = bsearchPrefix(x * 2, tl, m, l, r, agg, f); return ret <= r ? ret : bsearchPrefix(x * 2 + 1, m + 1, tr, l, r, agg, f); } template <class F> int bsearchSuffix(int x, int tl, int tr, int l, int r, Data &agg, F f) { if (r < tl || tr < l) return l - 1; if (tl != tr) propagate(x, tl, tr); if (l <= tl && tr <= r) { Data v = C::merge(agg, TR[x].val); if (!f(v)) { agg = v; return l - 1; } } if (tl == tr) return tl; int m = tl + (tr - tl) / 2; int ret = bsearchSuffix(x * 2 + 1, m + 1, tr, l, r, agg, f); return l <= ret ? ret : bsearchSuffix(x * 2, tl, m, l, r, agg, f); } template <class F> SegmentTreeBeats(int N, F f) : N(N), TR(N == 0 ? 0 : 1 << __lg(N * 4 - 1)) { if (N > 0) { build(1, 0, N - 1, f); } } template <class It> SegmentTreeBeats(It st, It en) : SegmentTreeBeats(en - st, [&] { return *st++; }) {} SegmentTreeBeats(int N, const Data &vdef) : SegmentTreeBeats(N, [&] { return vdef; }) {} void update(int l, int r, const Arg &v) { update(1, 0, N - 1, l, r, v); } Data query(int l, int r) { return query(1, 0, N - 1, l, r); } template <class F> int bsearchPrefix(int l, int r, F f) { Data agg = C::qdef(); return bsearchPrefix(1, 0, N - 1, l, r, agg, f); } template <class F> int bsearchSuffix(int l, int r, F f) { Data agg = C::qdef(); return bsearchSuffix(1, 0, N - 1, l, r, agg, f); } }; struct C { struct Data { ll sm, mx1, mx2, mn1, mn2; int mx1cnt, mn1cnt; }; struct Lazy { ll val, sm, mx, mn; bool operator != (const Lazy &v) const { if (val != v.val) return true; if (sm != v.sm) return true; if (mx != v.mx) return true; if (mn != v.mn) return true; return false; } }; using Arg = pair<ll, int>; static Data qdef() { Data ret; ret.sm = 0; ret.mx1 = ret.mx2 = LLONG_MIN; ret.mn1 = ret.mn2 = LLONG_MAX; ret.mx1cnt = ret.mn1cnt = 0; return ret; } static Lazy ldef() { Lazy ret; ret.val = ret.sm = 0; ret.mx = LLONG_MIN; ret.mn = LLONG_MAX; return ret; } static Data makeData(ll v) { Data ret = qdef(); ret.sm = ret.mx1 = ret.mn1 = v; ret.mx1cnt = ret.mn1cnt = 1; return ret; } static Lazy makeLazy(const Data &, const Arg &a) { Lazy ret = ldef(); if (a.second == 0) ret.mn = a.first; else if (a.second == 1) ret.mx = a.first; else ret.val = ret.sm = a.first; return ret; } static bool breakCond(const Data &d, const Arg &a) { if (a.second == 0) return d.mx1 <= a.first; else if (a.second == 1) return d.mn1 >= a.first; return false; } static bool tagCond(const Data &d, const Arg &a) { if (a.second == 0) return d.mx2 < a.first; else if (a.second == 1) return d.mn2 > a.first; return true; } static Data merge(const Data &l, const Data &r) { Data ret; ret.sm = l.sm + r.sm; if (l.mx1 > r.mx1) { ret.mx1 = l.mx1; ret.mx2 = max(l.mx2, r.mx1); ret.mx1cnt = l.mx1cnt; } else if (l.mx1 < r.mx1) { ret.mx1 = r.mx1; ret.mx2 = max(l.mx1, r.mx2); ret.mx1cnt = r.mx1cnt; } else { ret.mx1 = l.mx1; ret.mx2 = max(l.mx2, r.mx2); ret.mx1cnt = l.mx1cnt + r.mx1cnt; } if (l.mn1 < r.mn1) { ret.mn1 = l.mn1; ret.mn2 = min(l.mn2, r.mn1); ret.mn1cnt = l.mn1cnt; } else if (l.mn1 > r.mn1) { ret.mn1 = r.mn1; ret.mn2 = min(l.mn1, r.mn2); ret.mn1cnt = r.mn1cnt; } else { ret.mn1 = l.mn1; ret.mn2 = min(l.mn2, r.mn2); ret.mn1cnt = l.mn1cnt + r.mn1cnt; } return ret; } static Data applyLazy(Data l, const Lazy &r) { if (r.mx > l.mn1) { l.sm += (r.mx - l.mn1) * l.mn1cnt; if (l.mx1 == l.mn1) l.mx1 = r.mx; if (l.mx2 == l.mn1) l.mx2 = r.mx; l.mn1 = r.mx; } if (r.mn < l.mx1) { l.sm += (r.mn - l.mx1) * l.mx1cnt; if (l.mn1 == l.mx1) l.mn1 = r.mn; if (l.mn2 == l.mx1) l.mn2 = r.mn; l.mx1 = r.mn; } l.sm += r.sm; if (l.mx1 != LLONG_MIN) l.mx1 += r.val; if (l.mx2 != LLONG_MIN) l.mx2 += r.val; if (l.mn1 != LLONG_MAX) l.mn1 += r.val; if (l.mn2 != LLONG_MAX) l.mn2 += r.val; return l; } static Lazy getSegmentVal(Lazy v, int k) { v.sm *= k; return v; } static Lazy mergeLazy(Lazy l, const Lazy &r) { if (r.mx != LLONG_MIN) { l.mx = max(l.mx, r.mx - l.val); l.mn = max(l.mn, l.mx); } if (r.mn != LLONG_MAX) { l.mn = min(l.mn, r.mn - l.val); l.mx = min(l.mx, l.mn); } l.val += r.val; l.sm += r.sm; return l; } }; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // freopen("err.txt", "w", stderr); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, Q; cin >> N >> Q; vector<C::Data> A(N); for (auto &&a : A) { ll v; cin >> v; a = C::makeData(v); } SegmentTreeBeats<C> ST(A.begin(), A.end()); for (int i = 0; i < Q; i++) { int t, l, r; cin >> t >> l >> r; --r; if (t <= 2) { ll b; cin >> b; ST.update(l, r, make_pair(b, t)); } else cout << ST.query(l, r).sm << nl; } return 0; }