Submit Info #3059

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp kimiyuki AC 773 ms 39.14 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 0.63 MiB
max_random_00 AC 755 ms 39.13 MiB
max_random_01 AC 773 ms 39.12 MiB
max_random_02 AC 758 ms 39.14 MiB
medium_00 AC 7 ms 0.71 MiB
medium_01 AC 8 ms 0.59 MiB
medium_02 AC 7 ms 0.55 MiB
random_00 AC 516 ms 20.26 MiB
random_01 AC 555 ms 38.50 MiB
random_02 AC 371 ms 10.50 MiB
small_00 AC 6 ms 0.62 MiB
small_01 AC 7 ms 0.62 MiB
small_02 AC 5 ms 0.59 MiB
small_03 AC 5 ms 0.64 MiB
small_04 AC 5 ms 0.62 MiB
small_05 AC 5 ms 0.63 MiB
small_06 AC 6 ms 0.64 MiB
small_07 AC 6 ms 0.55 MiB
small_08 AC 4 ms 0.63 MiB
small_09 AC 6 ms 0.59 MiB

#line 1 "data_structure/segment_tree_beats.yosupo.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum" #line 2 "data_structure/segment_tree_beats.hpp" #include <algorithm> #include <cassert> #include <climits> #include <cstdint> #include <vector> #line 2 "utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 8 "data_structure/segment_tree_beats.hpp" /** * @brief a segment tree beats (range {chmin, chmax, add, update} + range {min, max, sum}) * @docs data_structure/segment_tree_beats.md * @see https://codeforces.com/blog/entry/57319 */ class segment_tree_beats { // MEMO: values for queries (max, min, lazy_add, and lazy_update) already apply to the current node; but not for children typedef struct { int64_t max; int64_t max_second; int max_count; int64_t min; int64_t min_second; int min_count; int64_t lazy_add; int64_t lazy_update; int64_t sum; } value_type; int n; std::vector<value_type> a; public: segment_tree_beats() = default; segment_tree_beats(int n_) { n = 1; while (n < n_) n *= 2; a.resize(2 * n - 1); tag<UPDATE>(0, 0); } template <class InputIterator> segment_tree_beats(InputIterator first, InputIterator last) { int n_ = std::distance(first, last); n = 1; while (n < n_) n *= 2; a.resize(2 * n - 1); REP (i, n_) { tag<UPDATE>(n - 1 + i, *(first + i)); } REP3 (i, n_, n) { tag<UPDATE>(n - 1 + i, 0); } REP_R (i, n - 1) { update(i); } } void range_chmin(int l, int r, int64_t value) { // 0-based, [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, int64_t value) { // 0-based, [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, int64_t value) { // 0-based, [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, int64_t value) { // 0-based, [l, r) assert (0 <= l and l <= r and r <= n); range_apply<UPDATE>(0, 0, n, l, r, value); } int64_t range_min(int l, int r) { // 0-based, [l, r) assert (0 <= l and l <= r and r <= n); return range_get<MIN>(0, 0, n, l, r); } int64_t range_max(int l, int r) { // 0-based, [l, r) assert (0 <= l and l <= r and r <= n); return range_get<MAX>(0, 0, n, l, r); } int64_t range_sum(int l, int r) { // 0-based, [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, int64_t 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, int64_t 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, int64_t 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, int64_t 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 != INT64_MIN) { 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 != INT64_MAX) { 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 != INT64_MAX) { 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 != INT64_MAX) { 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 != INT64_MAX) { a[i].max += g; } if (a[i].max_second != INT64_MIN) { a[i].max_second += g; } if (a[i].min != INT64_MIN) { a[i].min += g; } if (a[i].min_second != INT64_MAX) { a[i].min_second += g; } a[i].lazy_add += g; if (a[i].lazy_update != INT64_MAX) { a[i].lazy_update += g; } a[i].sum += g * length; } else if (TYPE == UPDATE) { a[i].max = g; a[i].max_second = INT64_MIN; a[i].max_count = length; a[i].min = g; a[i].min_second = INT64_MAX; a[i].min_count = length; a[i].lazy_add = 0; a[i].lazy_update = INT64_MAX; 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 != INT64_MAX) { tag<UPDATE>(l, a[i].lazy_update); tag<UPDATE>(r, a[i].lazy_update); a[i].lazy_update = INT64_MAX; 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<int64_t> 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<int64_t> 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 = INT64_MAX; // sum a[i].sum = a[l].sum + a[r].sum; } template <char TYPE> int64_t range_get(int i, int il, int ir, int l, int r) { if (ir <= l or r <= il) { switch (TYPE) { case MIN: return INT64_MAX; case MAX: return INT64_MIN; case SUM: return 0; default: assert (false); } } 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); int64_t value_l = range_get<TYPE>(2 * i + 1, il, (il + ir) / 2, l, r); int64_t 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); } } } }; #line 3 "data_structure/segment_tree_beats.yosupo.test.cpp" #include <cstdint> #include <vector> #line 2 "hack/fastio.hpp" #include <cstdint> #include <cstdio> #include <string> #include <type_traits> template <class Char, std::enable_if_t<std::is_same_v<Char, char>, int> = 0> inline Char in() { return getchar_unlocked(); } template <class String, std::enable_if_t<std::is_same_v<String, std::string>, int> = 0> inline std::string in() { std::string s; for (char c; not isspace(c = getchar_unlocked()); ) s.push_back(c); return s; } template <class Integer, std::enable_if_t<std::is_integral_v<Integer>, int> = 0> inline Integer in() { Integer n = getchar_unlocked() - '0'; if (std::is_signed<Integer>::value and n + '0' == '-') return -in<Integer>(); for (char c; (c = getchar_unlocked()) >= '0'; ) n = n * 10 + c - '0'; return n; } template <class Char, std::enable_if_t<std::is_same_v<Char, char>, int> = 0> inline void out(char c) { putchar_unlocked(c); } template <class String, std::enable_if_t<std::is_same_v<String, std::string>, int> = 0> inline void out(const std::string & s) { for (char c : s) putchar_unlocked(c); } template <class Integer, std::enable_if_t<std::is_integral_v<Integer>, int> = 0> inline void out(Integer n) { char s[20]; int i = 0; if (std::is_signed<Integer>::value and n < 0) { putchar_unlocked('-'); n *= -1; } do { s[i ++] = n % 10; n /= 10; } while (n); while (i) putchar_unlocked(s[-- i] + '0'); } #line 8 "data_structure/segment_tree_beats.yosupo.test.cpp" int main() { int n = in<int>(); int q = in<int>(); std::vector<int64_t> a(n); REP (i, n) { a[i] = in<int64_t>(); } segment_tree_beats beats(ALL(a)); while (q --) { int ty = in<int>(); int l = in<int>(); int r = in<int>(); if (ty == 0) { int64_t b = in<int64_t>(); beats.range_chmin(l, r, b); } else if (ty == 1) { int64_t b = in<int64_t>(); beats.range_chmax(l, r, b); } else if (ty == 2) { int64_t b = in<int64_t>(); beats.range_add(l, r, b); } else { int64_t sum = beats.range_sum(l, r); out<int64_t>(sum); out<char>('\n'); } } return 0; }