Submit Info #23533

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp nok0 AC 863 ms 39.25 MiB

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.61 MiB
max_random_00 AC 769 ms 39.09 MiB
max_random_01 AC 782 ms 39.15 MiB
max_random_02 AC 762 ms 39.17 MiB
medium_00 AC 3 ms 0.71 MiB
medium_01 AC 3 ms 0.68 MiB
medium_02 AC 3 ms 0.36 MiB
random2_00 AC 757 ms 39.25 MiB
random2_01 AC 783 ms 39.20 MiB
random2_02 AC 756 ms 39.23 MiB
random3_00 AC 859 ms 38.28 MiB
random3_01 AC 838 ms 38.20 MiB
random3_02 AC 863 ms 38.20 MiB
random_00 AC 505 ms 20.30 MiB
random_01 AC 548 ms 38.50 MiB
random_02 AC 342 ms 10.62 MiB
small_00 AC 2 ms 0.67 MiB
small_01 AC 2 ms 0.68 MiB
small_02 AC 1 ms 0.67 MiB
small_03 AC 1 ms 0.67 MiB
small_04 AC 1 ms 0.66 MiB
small_05 AC 1 ms 0.56 MiB
small_06 AC 1 ms 0.67 MiB
small_07 AC 0 ms 0.66 MiB
small_08 AC 1 ms 0.67 MiB
small_09 AC 0 ms 0.61 MiB

/** * author: nok0 * created: 2020.09.19 20:45:51 **/ #include<bits/stdc++.h> using namespace std; template <class T> struct SegmentTreeBeats{ private: size_t n, n_; const T MAX = std::numeric_limits<T>::max(); const T MIN = -MAX; std::vector<T> max_v, min_v, smax_v, smin_v, lz_upd, lz_ad, sigm, len; std::vector<int> max_c, min_c; void init(std::vector<T> &v){ n_ = v.size(), n = 1; while(n < n_) n *= 2; max_v.assign(n * 2 - 1, MIN); min_v.assign(n * 2 - 1, MAX); smax_v.assign(n * 2 - 1, MIN); smin_v.assign(n * 2 - 1, MAX); lz_upd.assign(n * 2 - 1, MAX); lz_ad.assign(n * 2 - 1, 0); len.assign(n * 2 - 1, n); sigm.assign(n * 2 - 1, 0); max_c.assign(n * 2 - 1, 1); min_c.assign(n * 2 - 1, 1); for(int i = 0; i < n - 1; i++) len[i * 2 + 1] = len[i * 2 + 2] = (len[i] >> 1); for(int i = 0; i < n_; i++) max_v[i + n - 1] = min_v[i + n - 1] = sigm[i + n - 1] = v[i]; for(int i = n - 2; i >= 0; i--) proc(i); } void proc(int i){ sigm[i] = sigm[i * 2 + 1] + sigm[i * 2 + 2]; max_v[i] = std::max(max_v[i * 2 + 1], max_v[i * 2 + 2]); if(max_v[i * 2 + 1] > max_v[i * 2 + 2]){ max_c[i] = max_c[i * 2 + 1]; smax_v[i] = std::max(smax_v[i * 2 + 1], max_v[i * 2 + 2]); } if(max_v[i * 2 + 1] < max_v[i * 2 + 2]){ max_c[i] = max_c[i * 2 + 2]; smax_v[i] = std::max(max_v[i * 2 + 1], smax_v[i * 2 + 2]); } if(max_v[i * 2 + 1] == max_v[i * 2 + 2]){ max_c[i] = max_c[i * 2 + 1] + max_c[i * 2 + 2]; smax_v[i] = std::max(smax_v[i * 2 + 1], smax_v[i * 2 + 2]); } min_v[i] = std::min(min_v[i * 2 + 1], min_v[i * 2 + 2]); if(min_v[i * 2 + 1] < min_v[i * 2 + 2]){ min_c[i] = min_c[i * 2 + 1]; smin_v[i] = std::min(smin_v[i * 2 + 1], min_v[i * 2 + 2]); } if(min_v[i * 2 + 1] > min_v[i * 2 + 2]){ min_c[i] = min_c[i * 2 + 2]; smin_v[i] = std::min(min_v[i * 2 + 1], smin_v[i * 2 + 2]); } if(min_v[i * 2 + 1] == min_v[i * 2 + 2]){ min_c[i] = min_c[i * 2 + 1] + min_c[i * 2 + 2]; smin_v[i] = std::min(smin_v[i * 2 + 1], smin_v[i * 2 + 2]); } } void eval(int i){ if(lz_upd[i] != MAX){ in_update(i * 2 + 1, lz_upd[i]); in_update(i * 2 + 2, lz_upd[i]); lz_upd[i] = MAX; return; } if(lz_ad[i]){ in_add(i * 2 + 1, lz_ad[i]); in_add(i * 2 + 2, lz_ad[i]); lz_ad[i] = 0; } if(max_v[i] < max_v[i * 2 + 1]) in_chmin(i * 2 + 1, max_v[i]); if(max_v[i] < max_v[i * 2 + 2]) in_chmin(i * 2 + 2, max_v[i]); if(min_v[i] > min_v[i * 2 + 1]) in_chmax(i * 2 + 1, min_v[i]); if(min_v[i] > min_v[i * 2 + 2]) in_chmax(i * 2 + 2, min_v[i]); } void in_update(int i, T x){ max_v[i] = min_v[i] = x; smax_v[i] = MIN, smin_v[i] = MAX; max_c[i] = min_c[i] = len[i]; sigm[i] = len[i] * x; lz_upd[i] = x, lz_ad[i] = 0; } void in_chmin(int i, T x){ sigm[i] += (x - max_v[i]) * max_c[i]; if(max_v[i] == min_v[i]) max_v[i] = min_v[i] = x; else if(max_v[i] == smin_v[i]) max_v[i] = smin_v[i] = x; else max_v[i] = x; if(lz_upd[i] != MAX and lz_upd[i] > x) lz_upd[i] = x; } void in_chmax(int i, T x){ sigm[i] += (x - min_v[i]) * min_c[i]; if(min_v[i] == max_v[i]) min_v[i] = max_v[i] = x; else if(min_v[i] == smax_v[i]) min_v[i] = smax_v[i] = x; else min_v[i] = x; if(lz_upd[i] != MAX and lz_upd[i] < x) lz_upd[i] = x; } void in_add(int i, T x){ max_v[i] += x, min_v[i] += x; if(smin_v[i] != MAX) smin_v[i] += x; if(smax_v[i] != MIN) smax_v[i] += x; sigm[i] += x * len[i]; if(lz_upd[i] != MAX) lz_upd[i] += x; lz_ad[i] += x; } void chmin(int i, int a, int b, int l, int r, T x){ if(b <= l or r <= a or x >= max_v[i]) return; if(a <= l and r <= b and smax_v[i] < x){ in_chmin(i, x); return; } eval(i); chmin(i * 2 + 1, a, b, l, (l + r) >> 1, x); chmin(i * 2 + 2, a, b, (l + r) >> 1, r, x); proc(i); } void chmax(int i, int a, int b, int l, int r, T x){ if(b <= l or r <= a or x <= min_v[i]) return; if(a <= l and r <= b and smin_v[i] > x){ in_chmax(i, x); return; } eval(i); chmax(i * 2 + 1, a, b, l, (l + r) >> 1, x); chmax(i * 2 + 2, a, b, (l + r) >> 1, r, x); proc(i); } void add(int i, int a, int b, int l, int r, T x){ if(b <= l or r <= a) return; if(a <= l and r <= b){ in_add(i, x); return; } eval(i); add(i * 2 + 1, a, b, l, (l + r) >> 1, x); add(i * 2 + 2, a, b, (l + r) >> 1, r, x); proc(i); } void update(int i, int a, int b, int l, int r, T x){ if(b <= l or r <= a) return; if(a <= l and r <= b){ in_update(i, x); return; } eval(i); update(i * 2 + 1, a, b, l, (l + r) >> 1, x); update(i * 2 + 2, a, b, (l + r) >> 1, r, x); proc(i); } T sum(int i, int a, int b, int l, int r) { if (r <= a || b <= l) return 0; if (a <= l && r <= b) return sigm[i]; eval(i); T lv = sum(i * 2 + 1, a, b, l, (l + r) / 2); T rv = sum(i * 2 + 2, a, b, (l + r) / 2, r); return lv + rv; } T rangemin(int i, int a, int b, int l, int r){ if(r <= a or b <= l) return MAX; if(a <= l and r <= b) return min_v[i]; eval(i); T lv = rangemin(i * 2 + 1, a, b, l, (l + r) >> 1); T rv = rangemin(i * 2 + 2, a, b, (l + r) >> 1, r); return std::min(lv, rv); } T rangemax(int i, int a, int b, int l, int r){ if(r <= a or b <= l) return MIN; if(a <= l and r <= b) return max_v[i]; eval(i); T lv = rangemax(i * 2 + 1, a, b, l, (l + r) >> 1); T rv = rangemax(i * 2 + 2, a, b, (l + r) >> 1, r); return std::max(lv, rv); } T rangesum(int i, int a, int b, int l, int r){ if(r <= a or b <= l) return 0; if(a <= l and r <= b) return sigm[i]; eval(i); T lv = rangesum(i * 2 + 1, a, b, l, (l + r) >> 1); T rv = rangesum(i * 2 + 2, a, b, (l + r) >> 1, r); return lv + rv; } public: SegmentTreeBeats() = default; SegmentTreeBeats(std::vector<T> &v){ init(v); } SegmentTreeBeats(size_t n, T init_data){ std::vector<T> v(n, init_data); init(v); } void update_chmin(int a, int b, T x){ chmin(0, a, b, 0, n, x); } void update_chmax(int a, int b, T x){ chmax(0, a, b, 0, n, x); } void update_add(int a, int b, T x){ add(0, a, b, 0, n, x); } void update_upd(int a, int b, T x){ update(0, a, b, 0, n, x); } T query_min(int a, int b){ return rangemin(0, a, b, 0, n); } T query_max(int a, int b){ return rangemax(0, a, b, 0, n); } T query_sum(int a, int b){ return rangesum(0, a, b, 0, n); } }; int main(){ int n, q; std::cin >> n >> q; std::vector<long long> a(n); for(int i = 0; i < n; i++) std::cin >> a[i]; SegmentTreeBeats<long long> Beats(a); while(q--){ int type, l, r; std::cin >> type >> l >> r; if(type == 0){ long long b; std::cin >> b; Beats.update_chmin(l, r, b); } if(type == 1){ long long b; std::cin >> b; Beats.update_chmax(l, r, b); } if(type == 2){ long long b; std::cin >> b; Beats.update_add(l, r, b); } if(type == 3) std::cout << Beats.query_sum(l, r) << '\n'; } }