Submit Info #3058

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp14 (anonymous) AC 1010 ms 39.13 MiB

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.55 MiB
max_random_00 AC 998 ms 39.05 MiB
max_random_01 AC 1010 ms 39.13 MiB
max_random_02 AC 989 ms 39.05 MiB
medium_00 AC 9 ms 0.75 MiB
medium_01 AC 8 ms 0.63 MiB
medium_02 AC 8 ms 0.67 MiB
random_00 AC 682 ms 20.25 MiB
random_01 AC 738 ms 38.51 MiB
random_02 AC 497 ms 10.50 MiB
small_00 AC 5 ms 0.62 MiB
small_01 AC 6 ms 0.66 MiB
small_02 AC 6 ms 0.58 MiB
small_03 AC 7 ms 0.63 MiB
small_04 AC 6 ms 0.66 MiB
small_05 AC 6 ms 0.63 MiB
small_06 AC 6 ms 0.54 MiB
small_07 AC 5 ms 0.55 MiB
small_08 AC 6 ms 0.62 MiB
small_09 AC 6 ms 0.55 MiB

//----------------------------templates #pragma GCC optimize ("Ofast") #pragma GCC target ("tune=native") #pragma GCC target ("avx") //---------------------------- #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define int ll #define FOR(i,j,n) for (int i=(int)(j);i<(n);i++) #define REP(i,n) for (int i=0;i<(int)(n);i++) #define REPS(i,n) for (int i=1;i<=(int)(n);i++) #define REPN(i,n) for (int i=(int)(n)-1;i>=0;i--) #define REPNS(i,n) for (int i=(int)(n);i>0;i--) #define I(n) scanf("%lld", &(n)) #define LL(n) scanf("%lld", &(n)) #define pb(n) push_back((n)) #define mp(i,j) make_pair((i),(j)) #define eb(i,j) emplace_back((i),(j)) #define y0 y3487465 #define y1 y8687969 #define j0 j1347829 #define j1 j234892 #define uniq(v) v.erase( unique(v.begin(), v.end()), v.end() ) #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) typedef vector<int> vi; typedef pair<int,int> pi; typedef vector<pi> vpi; typedef vector<vi> vvi; typedef vector<vpi> vvpi; typedef vector<vvi> vvvi; const int mod = 1000000007; //-------------------------------------------- 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 { int max; int max_second; int max_count; int min; int min_second; int min_count; int lazy_add; int lazy_update; int sum; } value_type; int n; 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_ = 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)); } FOR(i, n_, n) { tag<UPDATE>(n - 1 + i, 0); } REPN(i, n-1) { update(i); } } void range_chmin(int l, int r, int 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, int 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, int 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, int value) { // 0-based, [l, r) assert (0 <= l and l <= r and r <= n); range_apply<UPDATE>(0, 0, n, l, r, value); } int 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); } int 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); } int 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, int 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, int 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, int 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, int g) { int length = n >> (64 - __builtin_clzll(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 = min(a[i].min_second, g); if (a[i].lazy_update != INT64_MAX) { a[i].lazy_update = 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 = max(a[i].max_second, g); if (a[i].lazy_update != INT64_MAX) { a[i].lazy_update = 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 vector<int> b { a[l].max, a[l].max_second, a[r].max, a[r].max_second }; sort(b.rbegin(), b.rend()); uniq(b); 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 vector<int> c { a[l].min, a[l].min_second, a[r].min, a[r].min_second }; sort(all(c)); uniq(b); 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> int 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); int value_l = range_get<TYPE>(2 * i + 1, il, (il + ir) / 2, l, r); int value_r = range_get<TYPE>(2 * i + 2, (il + ir) / 2, ir, l, r); // mult switch (TYPE) { case MIN: return min(value_l, value_r); case MAX: return max(value_l, value_r); case SUM: return value_l + value_r; default: assert (false); } } } }; signed main(){ int n,q; int od,l,r,b; I(n); I(q); vi a(n); REP(i,n) I(a[i]); segment_tree_beats sb(all(a)); REP(_,q){ I(od); I(l); I(r); if (od == 0){ I(b); sb.range_chmin(l,r,b); } else if (od == 1){ I(b); sb.range_chmax(l,r,b); } else if (od == 2){ I(b); sb.range_add(l,r,b); } else { b = sb.range_sum(l,r); printf("%lld\n", b); } } }