Submit Info #57366

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp tokusakurai AC 739 ms 39.34 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.70 MiB
max_random_00 AC 592 ms 39.21 MiB
max_random_01 AC 648 ms 39.22 MiB
max_random_02 AC 636 ms 39.21 MiB
medium_00 AC 2 ms 0.84 MiB
medium_01 AC 2 ms 0.71 MiB
medium_02 AC 1 ms 0.71 MiB
random2_00 AC 624 ms 39.21 MiB
random2_01 AC 665 ms 39.21 MiB
random2_02 AC 649 ms 39.34 MiB
random3_00 AC 739 ms 38.34 MiB
random3_01 AC 717 ms 38.34 MiB
random3_02 AC 718 ms 38.34 MiB
random_00 AC 411 ms 20.34 MiB
random_01 AC 428 ms 38.58 MiB
random_02 AC 251 ms 10.59 MiB
small_00 AC 1 ms 0.71 MiB
small_01 AC 1 ms 0.61 MiB
small_02 AC 1 ms 0.71 MiB
small_03 AC 1 ms 0.71 MiB
small_04 AC 1 ms 0.61 MiB
small_05 AC 1 ms 0.61 MiB
small_06 AC 1 ms 0.71 MiB
small_07 AC 1 ms 0.70 MiB
small_08 AC 1 ms 0.61 MiB
small_09 AC 1 ms 0.71 MiB

#include <bits/stdc++.h> using namespace std; struct io_setup{ io_setup(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); } } io_setup; template<typename T> struct Segment_Tree_Beats{ vector<T> max_1, max_2, min_1, min_2; vector<int> max_cnt, min_cnt; vector<T> sum, add, upd; //addとupdはそれぞれ加算・更新の遅延配列 vector<int> L, R; const T INF_T; int n; Segment_Tree_Beats(const vector<T> &v) : INF_T(numeric_limits<T>::max()/2) { int m = v.size(); n = 1; while(n < m) n <<= 1; max_1.assign(2*n, -INF_T), max_2.assign(2*n, -INF_T), max_cnt.assign(2*n, 0); min_1.assign(2*n, INF_T), min_2.assign(2*n, INF_T), min_cnt.assign(2*n, 0); sum.assign(2*n, 0), add.assign(2*n, 0), upd.assign(2*n, INF_T); L.assign(2*n, 0), R.assign(2*n, n); for(int i = 1; i < n; i++){ L[2*i] = L[i], R[2*i] = (L[i]+R[i])/2; L[2*i+1] = (L[i]+R[i])/2, R[2*i+1] = R[i]; } for(int i = 0; i < m; i++) init_node(i, v[i]); for(int i = n-1; i > 0; i--) pull(i); } void init_node(int i, T x){ i += n; max_1[i] = x, max_cnt[i] = 1; min_1[i] = x, min_cnt[i] = 1; sum[i] = x; } void node_chmin(int i, const T &x){ //max_1[i] > x > max_2[i]のときのchmin sum[i] += (x-max_1[i])*max_cnt[i]; if(min_1[i] == max_1[i]) min_1[i] = x; if(min_2[i] == max_1[i]) min_2[i] = x; max_1[i] = x; if(upd[i] != INF_T && x < upd[i]) upd[i] = x; } void node_chmax(int i, const T &x){ //min_1[i] < x < min_2[i]のときのchmax sum[i] += (x-min_1[i])*min_cnt[i]; if(max_1[i] == min_1[i]) max_1[i] = x; if(max_2[i] == min_1[i]) max_2[i] = x; min_1[i] = x; if(upd[i] != INF_T && x > upd[i]) upd[i] = x; } void node_add(int i, const T &x){ //全体にadd if(max_1[i] != -INF_T) max_1[i] += x; if(max_2[i] != -INF_T) max_2[i] += x; if(min_1[i] != INF_T) min_1[i] += x; if(min_2[i] != INF_T) min_2[i] += x; sum[i] += x*(R[i]-L[i]); if(upd[i] != INF_T) upd[i] += x; add[i] += x; } void node_update(int i, const T &x){ //全体にupdate max_1[i] = x, max_2[i] = -INF_T, max_cnt[i] = R[i]-L[i]; min_1[i] = x, min_2[i] = INF_T, min_cnt[i] = R[i]-L[i]; upd[i] = x, add[i] = 0; } void push(int i){ //iから遅延評価を子に流す if(upd[i] != INF_T){ node_update(2*i, upd[i]); node_update(2*i+1, upd[i]); upd[i] = INF_T; return; } if(add[i] != 0){ node_add(2*i, add[i]); node_add(2*i+1, add[i]); add[i] = 0; } if(max_1[i] < max_1[2*i]) node_chmin(2*i, max_1[i]); if(min_1[i] > min_1[2*i]) node_chmax(2*i, min_1[i]); if(max_1[i] < max_1[2*i+1]) node_chmin(2*i+1, max_1[i]); if(min_1[i] > min_1[2*i+1]) node_chmax(2*i+1, min_1[i]); } void pull(int i){ //子の状態からiの状態を復元する int l = 2*i, r = 2*i+1; sum[i] = sum[l]+sum[r]; if(max_1[l] > max_1[r]){ max_1[i] = max_1[l], max_2[i] = max(max_2[l], max_1[r]); max_cnt[i] = max_cnt[l]; } else if(max_1[l] < max_1[r]){ max_1[i] = max_1[r], max_2[i] = max(max_1[l], max_2[r]); max_cnt[i] = max_cnt[r]; } else{ max_1[i] = max_1[l], max_2[i] = max(max_2[l], max_2[r]); max_cnt[i] = max_cnt[l]+max_cnt[r]; } if(min_1[l] < min_1[r]){ min_1[i] = min_1[l], min_2[i] = min(min_2[l], min_1[r]); min_cnt[i] = min_cnt[l]; } else if(min_1[l] > min_1[r]){ min_1[i] = min_1[r], min_2[i] = min(min_1[l], min_2[r]); min_cnt[i] = min_cnt[r]; } else{ min_1[i] = min_1[l], min_2[i] = min(min_2[l], min_2[r]); min_cnt[i] = min_cnt[l]+min_cnt[r]; } } void range_chmin(int a, int b, const T &x, int i = 1){ //[a,b)をxでchminする if(b <= L[i] || R[i] <= a || max_1[i] <= x) return; if(a <= L[i] && R[i] <= b && max_2[i] < x) node_chmin(i, x); else{ push(i); range_chmin(a, b, x, 2*i); range_chmin(a, b, x, 2*i+1); pull(i); } } void range_chmax(int a, int b, const T &x, int i = 1){ //[a,b)をxでchmaxする if(b <= L[i] || R[i] <= a || min_1[i] >= x) return; if(a <= L[i] && R[i] <= b && min_2[i] > x) node_chmax(i, x); else{ push(i); range_chmax(a, b, x, 2*i); range_chmax(a, b, x, 2*i+1); pull(i); } } void range_add(int a, int b, const T &x, int i = 1){ //[a,b)にxを加算する if(b <= L[i] || R[i] <= a) return; if(a <= L[i] && R[i] <= b) node_add(i, x); else{ push(i); range_add(a, b, x, 2*i); range_add(a, b, x, 2*i+1); pull(i); } } T range_max(int a, int b, int i = 1){ //[a,b)の最大値を求める if(b <= L[i] || R[i] <= a) return -INF_T; if(a <= L[i] && R[i] <= b) return max_1[i]; push(i); return max(range_max(a, b, 2*i), range_max(a, b, 2*i+1)); } T range_min(int a, int b, int i = 1){ //[a,b)の最小値を求める if(b <= L[i] || R[i] <= a) return INF_T; if(a <= L[i] && R[i] <= b) return min_1[i]; push(i); return min(range_min(a, b, 2*i), range_min(a, b, 2*i+1)); } T range_sum(int a, int b, int i = 1){ //[a,b)の和を求める if(b <= L[i] || R[i] <= a) return 0; if(a <= L[i] && R[i] <= b) return sum[i]; push(i); return range_sum(a, b, 2*i)+range_sum(a, b, 2*i+1); } }; int main(){ int N, Q; cin >> N >> Q; vector<long long> a(N); for(int i = 0; i < N; i++) cin >> a[i]; Segment_Tree_Beats<long long> seg(a); while(Q--){ int t, l, r; cin >> t >> l >> r; if(t == 0){ long long x; cin >> x; seg.range_chmin(l, r, x); } if(t == 1){ long long x; cin >> x; seg.range_chmax(l, r, x); } if(t == 2){ long long x; cin >> x; seg.range_add(l, r, x); } if(t == 3){ cout << seg.range_sum(l, r) << '\n'; } } }