Submit Info #45508

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp universe AC 1073 ms 39.26 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
max_random_00 AC 719 ms 39.18 MiB
max_random_01 AC 722 ms 39.08 MiB
max_random_02 AC 710 ms 39.11 MiB
medium_00 AC 3 ms 0.76 MiB
medium_01 AC 3 ms 0.68 MiB
medium_02 AC 3 ms 0.67 MiB
random2_00 AC 812 ms 39.21 MiB
random2_01 AC 813 ms 39.18 MiB
random2_02 AC 810 ms 39.26 MiB
random3_00 AC 1073 ms 38.22 MiB
random3_01 AC 1071 ms 38.30 MiB
random3_02 AC 1068 ms 38.30 MiB
random_00 AC 489 ms 20.33 MiB
random_01 AC 530 ms 38.52 MiB
random_02 AC 348 ms 10.54 MiB
small_00 AC 2 ms 0.67 MiB
small_01 AC 1 ms 0.66 MiB
small_02 AC 3 ms 0.68 MiB
small_03 AC 1 ms 0.70 MiB
small_04 AC 1 ms 0.62 MiB
small_05 AC 1 ms 0.71 MiB
small_06 AC 1 ms 0.68 MiB
small_07 AC 1 ms 0.37 MiB
small_08 AC 1 ms 0.68 MiB
small_09 AC 1 ms 0.65 MiB

#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(auto i=(a); i<(b); ++i) #define trav(a,x) for(auto& a: x) #define all(x) begin(x),end(x) #define sz(x) (int)size(x) #define PB push_back #define cauto const auto using ll = long long; using ld = long double; using pii = pair<int,int>; using vi = vector<int>; struct edge{int to;}; using graph = vector<vector<edge>>; // Source: https://github.com/yosupo06/library-checker-problems/blob/master/datastructure/range_chmin_chmax_add_range_sum/sol/correct.cpp constexpr auto LINF = numeric_limits<ll>::max() / 4; class STBeats { typedef struct { ll max, max_second; int max_count; ll min, min_second; int min_count; ll lazy_add, lazy_update, sum; } value_type; int n; std::vector<value_type> a; public: STBeats() = default; STBeats(int n_) { n = 1; while (n < n_) n *= 2; a.resize(2 * n - 1); tag<UPDATE>(0, 0); } STBeats(const auto& cont) : STBeats(all(cont)) {} template <class InputIterator> STBeats(InputIterator first, InputIterator last) { int n_ = std::distance(first, last); n = 1; while (n < n_) n *= 2; a.resize(2 * n - 1); rep(i, 0, n_) tag<UPDATE>(n - 1 + i, *(first + i)); rep(i, n_, n) tag<UPDATE>(n - 1 + i, 0); for (int i = n - 2; i >= 0; i--) update(i); } void range_chmin(int l, int r, ll value) { // [l, r) assert (0 <= l and l <= r and r <= n); range_apply<CHMIN>(0, 0, n, l, r, value); } void range_chmax(int l, int r, ll value) { // [l, r) assert (0 <= l and l <= r and r <= n); range_apply<CHMAX>(0, 0, n, l, r, value); } void range_add(int l, int r, ll value) { // [l, r) assert (0 <= l and l <= r and r <= n); range_apply<ADD>(0, 0, n, l, r, value); } void range_update(int l, int r, ll value) { // [l, r) assert (0 <= l and l <= r and r <= n); range_apply<UPDATE>(0, 0, n, l, r, value); } ll range_min(int l, int r) { // [l, r) assert (0 <= l and l <= r and r <= n); return range_get<MIN>(0, 0, n, l, r); } ll range_max(int l, int r) { // [l, r) assert (0 <= l and l <= r and r <= n); return range_get<MAX>(0, 0, n, l, r); } ll range_sum(int l, int r) { // [l, r) assert (0 <= l and l <= r and r <= n); return range_get<SUM>(0, 0, n, l, r); } private: static constexpr char CHMIN = 0; static constexpr char CHMAX = 1; static constexpr char ADD = 2; static constexpr char UPDATE = 3; static constexpr char MIN = 10; static constexpr char MAX = 11; static constexpr char SUM = 12; template <char TYPE> void range_apply(int i, int il, int ir, int l, int r, ll g) { if (ir <= l or r <= il or break_condition<TYPE>(i, g)) { // break } else if (l <= il and ir <= r and tag_condition<TYPE>(i, g)) { tag<TYPE>(i, g); } else { pushdown(i); range_apply<TYPE>(2 * i + 1, il, (il + ir) / 2, l, r, g); range_apply<TYPE>(2 * i + 2, (il + ir) / 2, ir, l, r, g); update(i); } } template <char TYPE> inline bool break_condition(int i, ll g) { switch (TYPE) { case CHMIN: return a[i].max <= g; case CHMAX: return g <= a[i].min; case ADD: return false; case UPDATE: return false; default: assert (false); } } template <char TYPE> inline bool tag_condition(int i, ll g) { switch (TYPE) { case CHMIN: return a[i].max_second < g and g < a[i].max; case CHMAX: return a[i].min < g and g < a[i].min_second; case ADD: return true; case UPDATE: return true; default: assert (false); } } template <char TYPE> inline void tag(int i, ll g) { int length = n >> (32 - __builtin_clz(i + 1) - 1); if (TYPE == CHMIN) { if (a[i].max == a[i].min or g <= a[i].min) { tag<UPDATE>(i, g); return; } if (a[i].max != -LINF) { a[i].sum -= a[i].max * a[i].max_count; } a[i].max = g; a[i].min_second = std::min(a[i].min_second, g); if (a[i].lazy_update != LINF) { a[i].lazy_update = std::min(a[i].lazy_update, g); } a[i].sum += g * a[i].max_count; } else if (TYPE == CHMAX) { if (a[i].max == a[i].min or a[i].max <= g) { tag<UPDATE>(i, g); return; } if (a[i].min != LINF) { a[i].sum -= a[i].min * a[i].min_count; } a[i].min = g; a[i].max_second = std::max(a[i].max_second, g); if (a[i].lazy_update != LINF) { a[i].lazy_update = std::max(a[i].lazy_update, g); } a[i].sum += g * a[i].min_count; } else if (TYPE == ADD) { if (a[i].max != LINF) { a[i].max += g; } if (a[i].max_second != -LINF) { a[i].max_second += g; } if (a[i].min != -LINF) { a[i].min += g; } if (a[i].min_second != LINF) { a[i].min_second += g; } a[i].lazy_add += g; if (a[i].lazy_update != LINF) { a[i].lazy_update += g; } a[i].sum += g * length; } else if (TYPE == UPDATE) { a[i].max = g; a[i].max_second = -LINF; a[i].max_count = length; a[i].min = g; a[i].min_second = LINF; a[i].min_count = length; a[i].lazy_add = 0; a[i].lazy_update = LINF; a[i].sum = g * length; } else assert (false); } void pushdown(int i) { int l = 2 * i + 1; int r = 2 * i + 2; // update if (a[i].lazy_update != LINF) { tag<UPDATE>(l, a[i].lazy_update); tag<UPDATE>(r, a[i].lazy_update); a[i].lazy_update = LINF; return; } // add if (a[i].lazy_add != 0) { tag<ADD>(l, a[i].lazy_add); tag<ADD>(r, a[i].lazy_add); a[i].lazy_add = 0; } // chmin if (a[i].max < a[l].max) tag<CHMIN>(l, a[i].max); if (a[i].max < a[r].max) tag<CHMIN>(r, a[i].max); // chmax if (a[l].min < a[i].min) tag<CHMAX>(l, a[i].min); if (a[r].min < a[i].min) tag<CHMAX>(r, a[i].min); } void update(int i) { int l = 2 * i + 1; int r = 2 * i + 2; // chmin std::vector<ll> b { a[l].max, a[l].max_second, a[r].max, a[r].max_second }; std::sort(b.rbegin(), b.rend()); b.erase(std::unique(all(b)), b.end()); a[i].max = b[0]; a[i].max_second = b[1]; a[i].max_count = (b[0] == a[l].max ? a[l].max_count : 0) + (b[0] == a[r].max ? a[r].max_count : 0); // chmax std::vector<ll> c { a[l].min, a[l].min_second, a[r].min, a[r].min_second }; std::sort(all(c)); c.erase(std::unique(all(c)), c.end()); a[i].min = c[0]; a[i].min_second = c[1]; a[i].min_count = (c[0] == a[l].min ? a[l].min_count : 0) + (c[0] == a[r].min ? a[r].min_count : 0); // add a[i].lazy_add = 0; // update a[i].lazy_update = LINF; // sum a[i].sum = a[l].sum + a[r].sum; } template <char TYPE> ll range_get(int i, int il, int ir, int l, int r) { if (ir <= l or r <= il) { return 0; } else if (l <= il and ir <= r) { // base switch (TYPE) { case MIN: return a[i].min; case MAX: return a[i].max; case SUM: return a[i].sum; default: assert (false); } } else { pushdown(i); ll value_l = range_get<TYPE>(2 * i + 1, il, (il + ir) / 2, l, r); ll value_r = range_get<TYPE>(2 * i + 2, (il + ir) / 2, ir, l, r); // mult switch (TYPE) { case MIN: return std::min(value_l, value_r); case MAX: return std::max(value_l, value_r); case SUM: return value_l + value_r; default: assert (false); } } } }; int32_t main() { cin.sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); cout << fixed << setprecision(15); int n, q; cin >> n >> q; vector<ll> a(n); trav(i, a) cin >> i; STBeats st(a); rep(it, 0, q) { int t; cin >> t; int l, r; cin >> l >> r; if (t == 3) { // sum range query auto res = st.range_sum(l, r); cout << res << '\n'; } else { ll b; cin >> b; if (t == 0) { // chmin range update st.range_chmin(l, r, b); } else if (t == 1) { // chmax range update st.range_chmax(l, r, b); } else if (t == 2) { // increment range update st.range_add(l, r, b); } else assert(false); } } }