Submit Info #16203

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp FlowerOfSorrow AC 586 ms 42.86 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
max_random_00 AC 580 ms 42.86 MiB
max_random_01 AC 586 ms 42.79 MiB
max_random_02 AC 575 ms 42.80 MiB
medium_00 AC 4 ms 0.80 MiB
medium_01 AC 5 ms 0.67 MiB
medium_02 AC 4 ms 0.72 MiB
random_00 AC 394 ms 27.67 MiB
random_01 AC 401 ms 32.37 MiB
random_02 AC 265 ms 12.20 MiB
small_00 AC 2 ms 0.67 MiB
small_01 AC 1 ms 0.67 MiB
small_02 AC 3 ms 0.68 MiB
small_03 AC 1 ms 0.67 MiB
small_04 AC 3 ms 0.67 MiB
small_05 AC 1 ms 0.68 MiB
small_06 AC 1 ms 0.68 MiB
small_07 AC 1 ms 0.66 MiB
small_08 AC 3 ms 0.67 MiB
small_09 AC 3 ms 0.67 MiB

#include "bits/stdc++.h" using namespace std; struct segnode{ long long maxv = numeric_limits<long long>::min() / 2; long long maxvcnt = 0; long long maxv2 = numeric_limits<long long>::min() / 2; long long minv = numeric_limits<long long>::max() / 2; long long minvcnt = 0; long long minv2 = numeric_limits<long long>::max() / 2; long long rsum = 0; long long sum() const{ return rsum + maxv * maxvcnt + (maxv == minv ? 0 : minv * minvcnt); } }; struct recursive_segment_tree{ int n; using L = array<long long, 3>; // Lazy type 0: set to min, 1: set to max, 2: add using Q = segnode; // Query type L apply_lazy(const L &lazy, const L &x, const array<int, 2> &r, const array<int, 2> &rr){ // r is a subset of rr return {clamp(lazy[0], x[0] - lazy[2], x[1] - lazy[2]), clamp(lazy[1], x[0] - lazy[2], x[1] - lazy[2]), lazy[2] + x[2]}; } // update lazy node representing r with rr Q merge(const Q &lval, const Q &rval, int l, int m, int r){ Q res; if(lval.maxv > rval.maxv){ res.maxv = lval.maxv, res.maxvcnt = lval.maxvcnt; res.maxv2 = max(lval.maxv2, rval.maxv); } else if(lval.maxv < rval.maxv){ res.maxv = rval.maxv, res.maxvcnt = rval.maxvcnt; res.maxv2 = max(rval.maxv2, lval.maxv); } else{ res.maxv = lval.maxv, res.maxvcnt = lval.maxvcnt + rval.maxvcnt; res.maxv2 = max(lval.maxv2, rval.maxv2); } if(lval.minv < rval.minv){ res.minv = lval.minv, res.minvcnt = lval.minvcnt; res.minv2 = min(lval.minv2, rval.minv); } else if(lval.minv > rval.minv){ res.minv = rval.minv, res.minvcnt = rval.minvcnt; res.minv2 = min(rval.minv2, lval.minv); } else{ res.minv = lval.minv, res.minvcnt = lval.minvcnt + rval.minvcnt; res.minv2 = min(lval.minv2, rval.minv2); } res.rsum = lval.sum() + rval.sum() - res.maxv * res.maxvcnt - (res.maxv == res.minv ? 0 : res.minv * res.minvcnt); return res; } // merge two nodes representing the intervals [l, m) and [m, r) Q apply(const Q &val, const L &x, const array<int, 2> &r, const array<int, 2> &rr){ // r is a subset of rr Q res(val); if(res.maxv == res.minv){ res.maxv = res.minv = clamp(res.maxv, x[0], x[1]) + x[2]; } else if(res.maxvcnt + res.minvcnt == r[1] - r[0]){ res.maxv = clamp(res.maxv, x[0], x[1]) + x[2]; res.minv = clamp(res.minv, x[0], x[1]) + x[2]; res.maxv2 = res.minv, res.minv2 = res.maxv; } else{ res.maxv = clamp(res.maxv, x[0], x[1]) + x[2]; res.minv = clamp(res.minv, x[0], x[1]) + x[2]; if(res.maxv2 != numeric_limits<long long>::min() / 2) res.maxv2 += x[2]; if(res.minv2 != numeric_limits<long long>::max() / 2) res.minv2 += x[2]; res.rsum += x[2] * (r[1] - r[0] - res.maxvcnt - res.minvcnt); } return res; } // apply to node representing r lazy node representing rr pair<L, Q> id{{numeric_limits<long long>::min() / 2, numeric_limits<long long>::max() / 2, 0}, {}}; Q init(int p){ return id.second; } vector<L> lazy; vector<Q> val; void push(int u, int l, int r){ // push the internal node u if(lazy[u] != id.first && u + 1 < n << 1){ int m = l + (r - l >> 1), v = u + 1, w = u + (m - l << 1); val[v] = apply(val[v], lazy[u], {l, m}, {l, r}); lazy[v] = apply_lazy(lazy[v], lazy[u], {l, m}, {l, r}); val[w] = apply(val[w], lazy[u], {m, r}, {l, r}); lazy[w] = apply_lazy(lazy[w], lazy[u], {m, r}, {l, r}); lazy[u] = id.first; } } void refresh(int u, int l, int r){ if(u + 1 < n << 1){ int m = l + (r - l >> 1), v = u + 1, w = u + (m - l << 1); val[u] = merge(val[v], val[w], l, m, r); } if(lazy[u] != id.first) val[u] = apply(val[u], lazy[u], {l, r}, {l, r}); } template<typename IT> recursive_segment_tree(IT begin, IT end): n(distance(begin, end)), lazy(n << 1, id.first), val(n << 1, id.second){ build(begin, end, 0, 0, n); } recursive_segment_tree(int n): n(n), lazy(n << 1, id.first), val(n << 1, id.second){ build(0, 0, n); } template<typename IT> void build(IT begin, IT end, int u, int l, int r){ if(l + 1 == r) val[u] = *begin; else{ int m = l + (r - l >> 1), v = u + 1, w = u + (m - l << 1); IT inter = begin + (end - begin >> 1); build(begin, inter, v, l, m), build(inter, end, w, m, r); val[u] = merge(val[v], val[w], l, m, r); } } void build(int u, int l, int r){ if(l + 1 == r) val[u] = init(l); else{ int m = l + (r - l >> 1), v = u + 1, w = u + (m - l << 1); build(v, l, m), build(w, m, r); val[u] = merge(val[v], val[w], l, m, r); } } template<bool First = true> void update_min(int ql, int qr, L x, int u = 0, int l = 0, int r = numeric_limits<int>::max()){ if(First) r = n; if(qr <= l || r <= ql || val[u].maxv <= x[1]) return; if(ql <= l && r <= qr && val[u].maxv2 < x[1]) val[u] = apply(val[u], x, {l, r}, {ql, qr}), lazy[u] = apply_lazy(lazy[u], x, {l, r}, {ql, qr}); else{ push(u, l, r); int m = l + (r - l >> 1), v = u + 1, w = u + (m - l << 1); update_min<false>(ql, qr, x, v, l, m), update_min<false>(ql, qr, x, w, m, r); refresh(u, l, r); } } // Apply x to values at [ql, qr) template<bool First = true> void update_max(int ql, int qr, L x, int u = 0, int l = 0, int r = numeric_limits<int>::max()){ if(First) r = n; if(qr <= l || r <= ql || val[u].minv >= x[0]) return; if(ql <= l && r <= qr && val[u].minv2 > x[0]) val[u] = apply(val[u], x, {l, r}, {ql, qr}), lazy[u] = apply_lazy(lazy[u], x, {l, r}, {ql, qr}); else{ push(u, l, r); int m = l + (r - l >> 1), v = u + 1, w = u + (m - l << 1); update_max<false>(ql, qr, x, v, l, m), update_max<false>(ql, qr, x, w, m, r); refresh(u, l, r); } } // Apply x to values at [ql, qr) template<bool First = true> void update_sum(int ql, int qr, L x, int u = 0, int l = 0, int r = numeric_limits<int>::max()){ if(First) r = n; if(qr <= l || r <= ql) return; if(ql <= l && r <= qr) val[u] = apply(val[u], x, {l, r}, {ql, qr}), lazy[u] = apply_lazy(lazy[u], x, {l, r}, {ql, qr}); else{ push(u, l, r); int m = l + (r - l >> 1), v = u + 1, w = u + (m - l << 1); update_sum<false>(ql, qr, x, v, l, m), update_sum<false>(ql, qr, x, w, m, r); refresh(u, l, r); } } // Apply x to values at [ql, qr) template<bool First = true> Q query(int ql, int qr, int u = 0, int l = 0, int r = numeric_limits<int>::max()){ if(First) r = n; if(qr <= l || r <= ql) return id.second; if(ql <= l && r <= qr) return val[u]; push(u, l, r); int m = l + (r - l >> 1), v = u + 1, w = u + (m - l << 1); return merge(query<false>(ql, qr, v, l, m), query<false>(ql, qr, w, m, r), max(ql, l), clamp(m, ql, qr), min(qr, r)); } // Get the query result for [ql, qr) }; int main(){ cin.tie(0)->sync_with_stdio(0); int n, qq; cin >> n >> qq; vector<segnode> a(n); for(auto i = 0; i < n; ++ i){ cin >> a[i].maxv; a[i].minv = a[i].maxv; a[i].maxvcnt = a[i].minvcnt = 1; } recursive_segment_tree tr(a.begin(), a.end()); while(qq --){ int type, l, r; cin >> type >> l >> r; if(type == 0){ long long x; cin >> x; tr.update_min(l, r, {numeric_limits<long long>::min() / 2, x, 0}); } else if(type == 1){ long long x; cin >> x; tr.update_max(l, r, {x, numeric_limits<long long>::max() / 2, 0}); } else if(type == 2){ long long x; cin >> x; tr.update_sum(l, r, {numeric_limits<long long>::min() / 2, numeric_limits<long long>::max() / 2, x}); } else{ cout << tr.query(l, r).sum() << "\n"; } } return 0; } /* */ //////////////////////////////////////////////////////////////////////////////////////// // // // Coded by Aeren // // // ////////////////////////////////////////////////////////////////////////////////////////