Submit Info #2656

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

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.65 MiB
max_random_00 AC 740 ms 39.17 MiB
max_random_01 AC 746 ms 39.13 MiB
max_random_02 AC 731 ms 39.08 MiB
medium_00 AC 9 ms 0.80 MiB
medium_01 AC 8 ms 0.67 MiB
medium_02 AC 8 ms 0.62 MiB
random_00 AC 502 ms 20.38 MiB
random_01 AC 552 ms 38.55 MiB
random_02 AC 366 ms 10.64 MiB
small_00 AC 6 ms 0.59 MiB
small_01 AC 5 ms 0.63 MiB
small_02 AC 4 ms 0.62 MiB
small_03 AC 6 ms 0.66 MiB
small_04 AC 6 ms 0.62 MiB
small_05 AC 4 ms 0.62 MiB
small_06 AC 5 ms 0.62 MiB
small_07 AC 5 ms 0.63 MiB
small_08 AC 5 ms 0.62 MiB
small_09 AC 6 ms 0.55 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 * @note range {chmin, chmax, add, update} + range {min, max, sum} */ 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) { 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); 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 "utils/fastio_scanner.hpp" #include <algorithm> #include <cassert> #include <cstdlib> #include <cstring> #include <string> #include <type_traits> #include <unistd.h> class scanner { static constexpr int N = 65536; static constexpr int K = 64; char buf[K + N]; int l = 0; int r = 0; void flush() { if (K < r - l) return; memmove(buf + K - (r - l), buf + l, r - l); l = K - (r - l); r = K + read(STDIN_FILENO, buf + K, N); assert (l < r); } void prepare() { flush(); while (isspace(buf[l])) { ++ l; flush(); } } public: scanner() = default; scanner(const scanner &) = delete; scanner & operator = (const scanner &) = delete; template <class Char, std::enable_if_t<std::is_same<Char, char>::value, int> = 0> inline char get() { prepare(); return buf[l ++]; } template <class String, std::enable_if_t<std::is_same<String, std::string>::value, int> = 0> std::string get() { prepare(); std::string s; do { s.push_back(buf[l ++]); if (r == l) flush(); } while (not isspace(buf[l])); return s; } template <class Integer, std::enable_if_t<std::is_integral<Integer>::value, int> = 0> Integer get() { prepare(); bool is_negative = false; if (std::is_signed<Integer>::value and buf[l] == '-') { is_negative = true; ++ l; } Integer x = 0; while (l < r and isdigit(buf[l])) { x *= 10; x += buf[l] - '0'; ++ l; } if (std::is_signed<Integer>::value and is_negative) { x *= -1; } return x; } }; #line 2 "utils/fastio_printer.hpp" #include <algorithm> #include <cstdlib> #include <cstring> #include <string> #include <type_traits> #include <unistd.h> class printer { static constexpr int N = 65536; static constexpr int K = 64; char buf[N]; int i = 0; inline void flush() { write(STDOUT_FILENO, buf, i); i = 0; } public: printer() = default; printer(const printer &) = delete; printer & operator = (const printer &) = delete; ~printer() { flush(); } template <class Char, std::enable_if_t<std::is_same<Char, char>::value, int> = 0> inline void put(char c) { if (i == N) flush(); buf[i ++] = c; } template <class String, std::enable_if_t<std::is_same<String, std::string>::value, int> = 0> void put(const std::string & s) { for (int l = 0; l < (int)s.length(); ) { if (i == N) flush(); int r = std::min<int>(s.length(), l + (N - i)); memcpy(buf + i, s.data() + l, r - l); i += r - l; l = r; } } template <class Integer, std::enable_if_t<std::is_integral<Integer>::value, int> = 0> void put(Integer x) { if (N - i < K) flush(); if (std::is_signed<Integer>::value and x < 0) { x *= -1; buf[i ++] = '-'; } if (x == 0) { buf[i ++] = '0'; return; } char s[K]; int j = 0; while (x) { s[j ++] = x % 10 + '0'; x /= 10; } while (j) { buf[i ++] = s[-- j]; } } }; #line 9 "data_structure/segment_tree_beats.yosupo.test.cpp" int main() { scanner sc; printer pr; int n = sc.get<int>(); int q = sc.get<int>(); std::vector<int64_t> a(n); REP (i, n) { a[i] = sc.get<int64_t>(); } segment_tree_beats beats(ALL(a)); while (q --) { int ty = sc.get<int>(); int l = sc.get<int>(); int r = sc.get<int>(); if (ty == 0) { int64_t b = sc.get<int64_t>(); beats.range_chmin(l, r, b); } else if (ty == 1) { int64_t b = sc.get<int64_t>(); beats.range_chmax(l, r, b); } else if (ty == 2) { int64_t b = sc.get<int64_t>(); beats.range_add(l, r, b); } else { int64_t sum = beats.range_sum(l, r); pr.put<int64_t>(sum); pr.put<char>('\n'); } } return 0; }