Submit Info #16202

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

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.72 MiB
max_random_00 AC 580 ms 42.80 MiB
max_random_01 AC 573 ms 42.80 MiB
max_random_02 AC 569 ms 42.85 MiB
medium_00 AC 4 ms 0.80 MiB
medium_01 AC 0 ms 0.74 MiB
medium_02 AC 5 ms 0.68 MiB
random_00 AC 398 ms 27.67 MiB
random_01 AC 409 ms 32.42 MiB
random_02 AC 264 ms 12.17 MiB
small_00 AC 1 ms 0.68 MiB
small_01 AC 3 ms 0.68 MiB
small_02 AC 1 ms 0.67 MiB
small_03 AC 3 ms 0.67 MiB
small_04 AC 2 ms 0.68 MiB
small_05 AC 3 ms 0.67 MiB
small_06 AC 0 ms 0.68 MiB
small_07 AC 2 ms 0.68 MiB
small_08 AC 2 ms 0.68 MiB
small_09 AC 2 ms 0.68 MiB

#include "bits/stdc++.h" using namespace std; // DEBUG BEGIN template<typename L, typename R> ostream &operator<<(ostream &out, pair<L, R> p){ return out << "(" << p.first << ", " << p.second << ")"; } template<class Tuple, size_t N> struct TuplePrinter{ static ostream &print(ostream &out, const Tuple &t){ return TuplePrinter<Tuple, N-1>::print(out, t) << ", " << get<N-1>(t); } }; template<class Tuple> struct TuplePrinter<Tuple, 1>{ static ostream &print(ostream &out, const Tuple& t){ return out << get<0>(t); } }; template<typename... Args> ostream &print_tuple(ostream &out, const tuple<Args...> &t){ return TuplePrinter<decltype(t), sizeof...(Args)>::print(out << "(", t) << ")"; } template<typename ...Args> ostream &operator<<(ostream &out, const tuple<Args...> &t){ return print_tuple(out, t); } template<typename ...Args, template<typename...> typename T> ostream &operator<<(enable_if_t<!is_same<T<Args...>, string>::value, ostream> &out, T<Args...> arr){ out << "{"; for(auto &x: arr) out << x << ", "; return out << (arr.size() ? "\b\b" : "") << "}"; } template<typename T, size_t N> ostream &operator<<(ostream &out, array<T, N> arr){ out << "{"; for(auto &x: arr) out << x << ", "; return out << (arr.size() ? "\b\b" : "") << "}"; } template<size_t S> ostream &operator<<(ostream &out, bitset<S> b){ for(int i = 0; i < S; ++ i) out << b[i]; return out; } void debug_out(){ cerr << "\b\b " << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cerr << H << ", ", debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif // DEBUG END 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); } void print() const{ debug(maxv, maxvcnt, maxv2); debug(minv, minvcnt, minv2); debug(rsum); } }; 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); debug("Merging", l, m); lval.print(); debug("with", m, r); rval.print(); debug("result", l, r); res.print(); debug("\n"); 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); } debug("updating", r); val.print(); debug("with", x); debug("result"); res.print(); debug("\n"); 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; debug("TYPE0", l, r, "\n"); tr.update_min(l, r, {numeric_limits<long long>::min() / 2, x, 0}); } else if(type == 1){ long long x; cin >> x; debug("TYPE1", l, r, x, "\n"); tr.update_max(l, r, {x, numeric_limits<long long>::max() / 2, 0}); } else if(type == 2){ long long x; cin >> x; debug("TYPE2", l, r, x, "\n"); tr.update_sum(l, r, {numeric_limits<long long>::min() / 2, numeric_limits<long long>::max() / 2, x}); } else{ debug("TYPE3", l, r, "\n"); cout << tr.query(l, r).sum() << "\n"; } } return 0; } /* 5 3 1 0 -1 5 3 2 0 4 -4 0 0 4 -3 3 4 5 [2 0 4 -4] 1 0 -1 5 3 -3 -4 -5 1 3 [0 0 4 -3] -3 -4 -5 -3 3 */ //////////////////////////////////////////////////////////////////////////////////////// // // // Coded by Aeren // // // ////////////////////////////////////////////////////////////////////////////////////////