:heavy_check_mark: verify/segment-tree/LC_range_chmin_chmax_add_range_sum.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum"

#include "template/template.hpp"
#include "segment-tree/range-chmin-chmax-add-range-sum.hpp"

int main() {
  int n, q;
  in(n, q);
  vector<ll> a(n);
  in(a);
  RangeChminChmaxAddRangeSum<ll> seg(a);
  while (q--) {
    int t, l, r;
    in(t, l, r);
    if (t == 0) {
      ll b;
      in(b);
      seg.chmin(l, r, b);
    } else if (t == 1) {
      ll b;
      in(b);
      seg.chmax(l, r, b);
    } else if (t == 2) {
      ll b;
      in(b);
      seg.add(l, r, b);
    } else {
      out(seg.sum(l, r));
    }
  }
}
#line 1 "verify/segment-tree/LC_range_chmin_chmax_add_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum"

#line 2 "template/template.hpp"

// repo: https://github.com/kumacs/library-cpp
// docs: https://kumacs.github.io/library-cpp

#include <bits/stdc++.h>
using namespace std;

#line 2 "template/macro.hpp"
#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b) - 1; i >= (a); i--)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())
#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())
#define YN(b) cout << ((b) ? "YES" : "NO") << "\n";
#define Yn(b) cout << ((b) ? "Yes" : "No") << "\n";
#define yn(b) cout << ((b) ? "yes" : "no") << "\n";
#line 10 "template/template.hpp"

#line 2 "template/util.hpp"
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
template <class T>
using priority_queue_asc = priority_queue<T, vector<T>, greater<T>>;

template <class T, class S = T>
S SUM(const vector<T>& a) {
  return accumulate(ALL(a), S(0));
}
template <class T1, class T2>
inline bool chmin(T1& a, T2 b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T1, class T2>
inline bool chmax(T1& a, T2 b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T1, class T2>
inline bool chmin_opt(optional<T1>& a, T2 b) {
  if (!a || a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T1, class T2>
inline bool chmax_opt(optional<T1>& a, T2 b) {
  if (!a || a < b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
int popcnt(T x) {
  return __builtin_popcountll(x);
}
template <class T>
int topbit(T x) {
  return (x == 0 ? -1 : 63 - __builtin_clzll(x));
}
template <class T>
int lowbit(T x) {
  return (x == 0 ? -1 : __builtin_ctzll(x));
}
#line 12 "template/template.hpp"

#line 2 "template/inout.hpp"
struct Fast {
  Fast() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
  }
} fast;

ostream& operator<<(ostream& os, __uint128_t x) {
  char buf[40];
  size_t k = 0;
  while (x > 0) buf[k++] = (char)(x % 10 + '0'), x /= 10;
  if (k == 0) buf[k++] = '0';
  while (k) os << buf[--k];
  return os;
}
ostream& operator<<(ostream& os, __int128_t x) {
  return x < 0 ? (os << '-' << (__uint128_t)(-x)) : (os << (__uint128_t)x);
}
template <class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N>& a);
template <class T1, class T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
  return is >> p.first >> p.second;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << p.first << " " << p.second;
}
template <class T>
istream& operator>>(istream& is, vector<T>& a) {
  for (auto& v : a) is >> v;
  return is;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& a) {
  for (auto it = a.begin(); it != a.end();) {
    os << *it;
    if (++it != a.end()) os << " ";
  }
  return os;
}
template <class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N>& a) {
  for (auto it = a.begin(); it != a.end();) {
    os << *it;
    if (++it != a.end()) os << " ";
  }
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& st) {
  os << "{";
  for (auto it = st.begin(); it != st.end();) {
    os << *it;
    if (++it != st.end()) os << ",";
  }
  os << "}";
  return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const map<T1, T2>& mp) {
  os << "{";
  for (auto it = mp.begin(); it != mp.end();) {
    os << it->first << ":" << it->second;
    if (++it != mp.end()) os << ",";
  }
  os << "}";
  return os;
}

void in() {}
template <typename T, class... U>
void in(T& t, U&... u) {
  cin >> t;
  in(u...);
}
template <class... T>
void in_zip(int n, T&... t) {
  assert(n >= 0 && ((size(t) >= static_cast<size_t>(n)) && ...));
  for (int i = 0; i < n; i++) in(t[i]...);
}
void out() { cout << "\n"; }
template <typename T, class... U, char sep = ' '>
void out(const T& t, const U&... u) {
  cout << t;
  if (sizeof...(u)) cout << sep;
  out(u...);
}
template <class T, class U>
void out_opt(const optional<T>& opt, const U& fallback, ostream& os = cout) {
  if (opt.has_value())
    os << opt.value();
  else
    os << fallback;
  os << "\n";
}
template <class T, class U>
void out_opt(const vector<optional<T>>& vec, const U& fallback, ostream& os = cout) {
  for (auto it = vec.begin(); it != vec.end();) {
    if ((*it).has_value())
      os << (*it).value();
    else
      os << fallback;
    if (++it != vec.end()) os << " ";
  }
  os << "\n";
}

namespace IO {
template <class T, class... U>
T read(U&&... u) {
  T t = T(forward<U>(u)...);
  in(t);
  return t;
}
namespace Graph {
vector<vector<int>> unweighted(int n, int m, bool directed = false, int offset = 1) {
  vector<vector<int>> g(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u -= offset, v -= offset;
    g[u].push_back(v);
    if (!directed) g[v].push_back(u);
  }
  return g;
}
template <class T>
vector<vector<pair<int, T>>> weighted(int n, int m, bool directed = false, int offset = 1) {
  vector<vector<pair<int, T>>> g(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    T w;
    cin >> u >> v >> w;
    u -= offset, v -= offset;
    g[u].push_back({v, w});
    if (!directed) g[v].push_back({u, w});
  }
  return g;
}
}  // namespace Graph
namespace Tree {
vector<vector<int>> unweighted(int n, bool directed = false, int offset = 1) {
  return Graph::unweighted(n, n - 1, directed, offset);
}
template <class T>
vector<vector<pair<int, T>>> weighted(int n, bool directed = false, int offset = 1) {
  return Graph::weighted<T>(n, n - 1, directed, offset);
}
vector<vector<int>> rooted(int n, bool to_root = true, bool to_leaf = true, int offset = 1) {
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    int p;
    cin >> p;
    p -= offset;
    if (to_root) g[i].push_back(p);
    if (to_leaf) g[p].push_back(i);
  }
  return g;
}
}  // namespace Tree
}  // namespace IO
#line 14 "template/template.hpp"

#line 2 "template/debug.hpp"
#ifdef LOCAL
#define debug 1
#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)
#else
#define debug 0
#define show(...) true
#endif
template <class T>
void _show(int, T) {
  cerr << '\n';
}
template <class T1, class T2, class... T3>
void _show(int i, const T1& a, const T2& b, const T3&... c) {
  for (; a[i] != ',' && a[i] != '\0'; i++) cerr << a[i];
  cerr << ":" << b << " ";
  _show(i + 1, a, c...);
}
#line 2 "segment-tree/range-chmin-chmax-add-range-sum.hpp"

#line 2 "algebraic-structure/util.hpp"
#ifdef __cpp_concepts
#define REQUIRES(...) requires __VA_ARGS__
#else
#define REQUIRES(...)
#endif
#line 3 "algebraic-structure/magma.hpp"

#ifdef __cpp_concepts
template <class M>
concept Magma = requires(typename M::value_type x, typename M::value_type y) {
  typename M::value_type;
  { M::op(x, y) } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMagma {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
};
template <class T>
struct MulMagma {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
};
template <class T, T id>
struct MaxMagma {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
};
template <class T, T id>
struct MinMagma {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
};
#line 3 "algebraic-structure/monoid.hpp"

#ifdef __cpp_concepts
template <class M>
concept Monoid = Magma<M> && requires {
  { M::e() } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMonoid {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
  static T e() { return T(0); }
};
template <class T>
struct MulMonoid {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
  static T e() { return T(1); }
};
template <class T, T id>
struct MaxMonoid {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
  static T e() { return id; }
};
template <class T, T id>
struct MinMonoid {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
  static T e() { return id; }
};
#line 3 "algebraic-structure/monoid-action.hpp"

#ifdef __cpp_concepts
template <class A>
concept MonoidAction = Monoid<typename A::value_monoid> && Monoid<typename A::operator_monoid> && requires(typename A::value_monoid::value_type x, typename A::operator_monoid::value_type f) {
  typename A::value_monoid;
  typename A::operator_monoid;
  { A::mapping(f, x) } -> same_as<typename A::value_monoid::value_type>;
};
#endif
#line 3 "segment-tree/lazy-segment-tree.hpp"

template <class A>
REQUIRES(MonoidAction<A>)
struct LazySegmentTree {
  using VM = typename A::value_monoid;
  using OM = typename A::operator_monoid;
  using T = typename VM::value_type;
  using F = typename OM::value_type;

 protected:
  int _n, size, log;
  vector<T> d;
  vector<F> lz;

  void update(int k) { d[k] = VM::op(d[2 * k], d[2 * k + 1]); }
  virtual void all_apply(int k, F f) {
    d[k] = A::mapping(f, d[k]);
    if (k < size) lz[k] = OM::op(f, lz[k]);
  }
  void push(int k) {
    all_apply(2 * k, lz[k]);
    all_apply(2 * k + 1, lz[k]);
    lz[k] = OM::e();
  }

 public:
  LazySegmentTree() : LazySegmentTree(0) {}
  explicit LazySegmentTree(int n) : LazySegmentTree(vector<T>(n, VM::e())) {}
  explicit LazySegmentTree(const vector<T>& v) : _n(int(v.size())) {
    size = 1, log = 0;
    while (size < _n) size <<= 1, log++;
    d = vector<T>(2 * size, VM::e());
    lz = vector<F>(size, OM::e());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i > 0; i--) update(i);
  }
  virtual ~LazySegmentTree() = default;

  void set(int p, T x) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    d[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  T get(int p) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    return d[p];
  }
  T prod(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return VM::e();
    l += size, r += size;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    T sml = VM::e(), smr = VM::e();
    while (l < r) {
      if (l & 1) sml = VM::op(sml, d[l++]);
      if (r & 1) smr = VM::op(d[--r], smr);
      l >>= 1, r >>= 1;
    }
    return VM::op(sml, smr);
  }
  T all_prod() { return d[1]; }
  void apply(int p, F f) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    d[p] = A::mapping(f, d[p]);
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  void apply(int l, int r, F f) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return;
    l += size, r += size;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    {
      int l2 = l, r2 = r;
      while (l < r) {
        if (l & 1) all_apply(l++, f);
        if (r & 1) all_apply(--r, f);
        l >>= 1, r >>= 1;
      }
      l = l2, r = r2;
    }
    for (int i = 1; i <= log; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
  }
  template <bool (*g)(T)>
  int max_right(int l) {
    return max_right(l, [](T x) { return g(x); });
  }
  template <class G>
  int max_right(int l, G g) {
    assert(0 <= l && l <= _n);
    assert(g(VM::e()));
    if (l == _n) return _n;
    l += size;
    for (int i = log; i >= 1; i--) push(l >> i);
    T sm = VM::e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!g(VM::op(sm, d[l]))) {
        while (l < size) {
          push(l);
          l = (2 * l);
          if (g(VM::op(sm, d[l]))) sm = VM::op(sm, d[l++]);
        }
        return l - size;
      }
      sm = VM::op(sm, d[l++]);
    } while ((l & -l) != l);
    return _n;
  }

  template <bool (*g)(T)>
  int min_left(int r) {
    return min_left(r, [](T x) { return g(x); });
  }
  template <class G>
  int min_left(int r, G g) {
    assert(0 <= r && r <= _n);
    assert(g(VM::e()));
    if (r == 0) return 0;
    r += size;
    for (int i = log; i >= 1; i--) push((r - 1) >> i);
    T sm = VM::e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!g(VM::op(d[r], sm))) {
        while (r < size) {
          push(r);
          r = (2 * r + 1);
          if (g(VM::op(d[r], sm))) sm = VM::op(d[r--], sm);
        }
        return r + 1 - size;
      }
      sm = VM::op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }
};

/**
 * @brief Lazy Segment Tree
 * @docs docs/segment-tree/lazy-segment-tree.md
 */
#line 3 "segment-tree/segment-tree-beats.hpp"

template <class A>
REQUIRES(MonoidAction<A>)
struct SegmentTreeBeats : LazySegmentTree<A> {
  using base = LazySegmentTree<A>;
  using T = typename base::T;
  using F = typename base::F;

  SegmentTreeBeats() : base() {}
  explicit SegmentTreeBeats(int n) : base(n) {}
  explicit SegmentTreeBeats(const vector<T>& v) : base(v) {}

 protected:
  void all_apply(int k, F f) override {
    this->d[k] = A::mapping(f, this->d[k]);
    if (k < this->size) {
      this->lz[k] = base::OM::op(f, this->lz[k]);
      if (this->d[k].fail) this->push(k), this->update(k);
    }
  }
};

/**
 * @brief Segment Tree Beats
 * @docs docs/segment-tree/segment-tree-beats.md
 */
#line 4 "segment-tree/range-chmin-chmax-add-range-sum.hpp"

namespace RangeChminChmaxAddRangeSumImpl {
template <class T>
struct S {
  static_assert(numeric_limits<T>::is_integer && numeric_limits<T>::is_signed);
  static constexpr T INF = numeric_limits<T>::max() / 4;
  T lo, hi, lo2, hi2, sum;
  int sz, nlo, nhi;
  bool fail;
  S() : lo(INF), hi(-INF), lo2(INF), hi2(-INF), sum(0), sz(0), nlo(0), nhi(0), fail(false) {}
  S(T x, int sz_) : lo(x), hi(x), lo2(INF), hi2(-INF), sum(x * sz_), sz(sz_), nlo(sz_), nhi(sz_), fail(false) {}
};
template <class T>
T second_lowest(T a, T a2, T b, T b2) {
  return a == b ? min(a2, b2) : a2 <= b ? a2 : b2 <= a ? b2 : max(a, b);
}
template <class T>
T second_highest(T a, T a2, T b, T b2) {
  return a == b ? max(a2, b2) : a2 >= b ? a2 : b2 >= a ? b2 : min(a, b);
}
template <class T>
struct ValueMonoid {
  using value_type = S<T>;
  static S<T> op(S<T> l, S<T> r) {
    S<T> x;
    x.lo = min(l.lo, r.lo), x.hi = max(l.hi, r.hi);
    x.lo2 = second_lowest(l.lo, l.lo2, r.lo, r.lo2);
    x.hi2 = second_highest(l.hi, l.hi2, r.hi, r.hi2);
    x.sum = l.sum + r.sum, x.sz = l.sz + r.sz;
    x.nlo = l.nlo * (l.lo <= r.lo) + r.nlo * (r.lo <= l.lo);
    x.nhi = l.nhi * (l.hi >= r.hi) + r.nhi * (r.hi >= l.hi);
    return x;
  }
  static S<T> e() { return S<T>(); }
};
template <class T>
struct F {
  T lb, ub, bias;
  F(T lb_ = -S<T>::INF, T ub_ = S<T>::INF, T bias_ = 0) : lb(lb_), ub(ub_), bias(bias_) {}
  static F chmin(T x) { return F(-S<T>::INF, x, 0); }
  static F chmax(T x) { return F(x, S<T>::INF, 0); }
  static F add(T x) { return F(-S<T>::INF, S<T>::INF, x); }
};
template <class T>
struct OperatorMonoid {
  using value_type = F<T>;
  static F<T> op(F<T> f, F<T> g) {
    F<T> h;
    h.lb = max(min(g.lb + g.bias, f.ub), f.lb) - g.bias;
    h.ub = min(max(g.ub + g.bias, f.lb), f.ub) - g.bias;
    h.bias = g.bias + f.bias;
    return h;
  }
  static F<T> e() { return F<T>(); }
};
template <class T>
struct Action {
  using value_monoid = ValueMonoid<T>;
  using operator_monoid = OperatorMonoid<T>;
  static S<T> mapping(F<T> f, S<T> x) {
    if (x.sz == 0) return S<T>();
    if (x.lo == x.hi || f.lb == f.ub || f.lb >= x.hi || f.ub <= x.lo) {
      return S<T>(min(max(x.lo, f.lb), f.ub) + f.bias, x.sz);
    }
    if (x.lo2 == x.hi) {
      x.lo = x.hi2 = max(x.lo, f.lb) + f.bias;
      x.hi = x.lo2 = min(x.hi, f.ub) + f.bias;
      x.sum = x.lo * x.nlo + x.hi * x.nhi;
      return x;
    }
    if (f.lb < x.lo2 && f.ub > x.hi2) {
      T next_lo = max(x.lo, f.lb), next_hi = min(x.hi, f.ub);
      x.sum += (next_lo - x.lo) * x.nlo - (x.hi - next_hi) * x.nhi + f.bias * x.sz;
      x.lo = next_lo + f.bias, x.hi = next_hi + f.bias;
      x.lo2 += f.bias, x.hi2 += f.bias;
      return x;
    }
    x.fail = true;
    return x;
  }
};
template <class T>
vector<S<T>> init(const vector<T>& a) {
  vector<S<T>> v;
  v.reserve(a.size());
  for (T x : a) v.emplace_back(x, 1);
  return v;
}
}  // namespace RangeChminChmaxAddRangeSumImpl

template <class T>
struct RangeChminChmaxAddRangeSum : SegmentTreeBeats<RangeChminChmaxAddRangeSumImpl::Action<T>> {
  using Impl = RangeChminChmaxAddRangeSumImpl::Action<T>;
  using S = RangeChminChmaxAddRangeSumImpl::S<T>;
  using F = RangeChminChmaxAddRangeSumImpl::F<T>;
  using base = SegmentTreeBeats<Impl>;
  RangeChminChmaxAddRangeSum() : base() {}
  explicit RangeChminChmaxAddRangeSum(int n) : base(vector<S>(n, S(T(0), 1))) {}
  explicit RangeChminChmaxAddRangeSum(const vector<T>& a) : base(RangeChminChmaxAddRangeSumImpl::init(a)) {}
  void set(int p, T x) { base::set(p, S(x, 1)); }
  T get(int p) { return base::get(p).sum; }
  void chmin(int l, int r, T x) { base::apply(l, r, F::chmin(x)); }
  void chmax(int l, int r, T x) { base::apply(l, r, F::chmax(x)); }
  void add(int l, int r, T x) { base::apply(l, r, F::add(x)); }
  T sum(int l, int r) { return base::prod(l, r).sum; }
  T prod(int l, int r) { return sum(l, r); }
  T all_sum() { return base::all_prod().sum; }
  T all_prod() { return all_sum(); }
};

/**
 * @brief Range Chmin Chmax Add Range Sum
 * @docs docs/segment-tree/range-chmin-chmax-add-range-sum.md
 */
#line 5 "verify/segment-tree/LC_range_chmin_chmax_add_range_sum.test.cpp"

int main() {
  int n, q;
  in(n, q);
  vector<ll> a(n);
  in(a);
  RangeChminChmaxAddRangeSum<ll> seg(a);
  while (q--) {
    int t, l, r;
    in(t, l, r);
    if (t == 0) {
      ll b;
      in(b);
      seg.chmin(l, r, b);
    } else if (t == 1) {
      ll b;
      in(b);
      seg.chmax(l, r, b);
    } else if (t == 2) {
      ll b;
      in(b);
      seg.add(l, r, b);
    } else {
      out(seg.sum(l, r));
    }
  }
}
Back to top page