Submit Info #23530

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

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
max_random_00 AC 785 ms 39.17 MiB
max_random_01 AC 791 ms 39.17 MiB
max_random_02 AC 771 ms 39.12 MiB
medium_00 AC 4 ms 0.80 MiB
medium_01 AC 3 ms 0.64 MiB
medium_02 AC 3 ms 0.67 MiB
random_00 AC 533 ms 20.36 MiB
random_01 AC 566 ms 38.55 MiB
random_02 AC 356 ms 10.62 MiB
small_00 AC 1 ms 0.57 MiB
small_01 AC 1 ms 0.64 MiB
small_02 AC 1 ms 0.66 MiB
small_03 AC 1 ms 0.65 MiB
small_04 AC 3 ms 0.67 MiB
small_05 AC 1 ms 0.61 MiB
small_06 AC 2 ms 0.66 MiB
small_07 AC 1 ms 0.67 MiB
small_08 AC 1 ms 0.67 MiB
small_09 AC 3 ms 0.64 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 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); } */ 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]); } 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; } void chmin(int i, int a, int b, int l, int r, T x) { if (b <= l || r <= a || x >= max_v[i]) return; if (a <= l && r <= b && smax_v[i] < x) { in_chmin(i, x); return; }//ここの値を直す。だけ。 eval(i);//子供の値も正しくする chmin(i * 2 + 1, a, b, l, (l + r) / 2, x); chmin(i * 2 + 2, a, b, (l + r) / 2, r, x); proc(i); } void chmax(int i, int a, int b, int l, int r, T x) { if (b <= l || r <= a || x <= min_v[i]) return; if (a <= l && r <= b && smin_v[i] > x) { in_chmax(i, x); return; }//ここの値を直す。だけ。 eval(i);//子供の値も正しくする chmax(i * 2 + 1, a, b, l, (l + r) / 2, x); chmax(i * 2 + 2, a, b, (l + r) / 2, r, x); proc(i); } void add(int i, int a, int b, int l, int r, T x) { if (b <= l || r <= a) return; if (a <= l && r <= b) { in_add(i, x); return; }//ここの値を直す。だけ。 eval(i);//子供の値も正しくする add(i * 2 + 1, a, b, l, (l + r) / 2, x); add(i * 2 + 2, a, b, (l + r) / 2, r, x); proc(i); } void update(int i, int a, int b, int l, int r, T x) { if (b <= l || r <= a) return; if (a <= l && r <= b) { in_update(i, x); return; }//ここの値を直す。だけ。 eval(i);//子供の値も正しくする update(i * 2 + 1, a, b, l, (l + r) / 2, x); update(i * 2 + 2, a, b, (l + r) / 2, r, x); proc(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_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 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 && 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]) max_v[i] = min_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 && lz_upd[i] < x) lz_upd[i] = x; } //check済み 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'; /*if(type == 3) continue; for(int i = 0; i < n; i++) std::cout<<Beats.query_sum(i, i + 1) << " "; std::cout<<std::endl;*/ } }