Skip to content

segment_tree_beats.hpp

SECTIONData Structure INCLUDEnoya/segment_tree_beats.hpp

维护区间 chmin、chmax、加法与区间和/最值；适合普通懒标记无法直接表示的截断更新。

Complexity: Time: O(n) build; amortized O(log^2 n) chmin/chmax and O(log n) add/query. Space: O(n).

AC 记录：range_add_range_min, range_chmin_chmax_add_range_sum。

跳到代码 · GitHub ↗

Implementation

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n) build; amortized O(log^2 n) chmin/chmax and O(log n) add/query.
/// Space: O(n).

#include <algorithm>
#include <cassert>
#include <limits>
#include <vector>

namespace noya {

/// @brief Segment Tree Beats supporting range add, chmin, chmax, sum, minimum,
/// and maximum queries; bound updates run in amortized O(log^2 n) time.
template <class T> struct segment_tree_beats {
  struct node {
    // mx/mn: extrema; mx2/mn2: strict second extrema; cmx/cmn: multiplicities.
    T sum{};
    T mx{};
    T mx2{};
    T mn{};
    T mn2{};
    T add{};
    int cmx = 0;
    int cmn = 0;
    int len = 0;
    bool hmx = false;
    bool hmn = false;
  };

  int n = 0;
  std::vector<node> tr;

  segment_tree_beats() = default;
  explicit segment_tree_beats(const std::vector<T> &a) { build(a); }

  /// @brief Rebuild from array a in O(n) time.
  void build(const std::vector<T> &a) {
    n = int(a.size());
    tr.assign(std::max(1, 4 * n), {});
    if (n > 0) {
      build_at(1, 0, n, a);
    }
  }

  /// @brief Add x to every element of [l, r).
  void range_add(int l, int r, const T &x) {
    check_range(l, r);
    if (l < r) {
      range_add_at(1, 0, n, l, r, x);
    }
  }

  /// @brief Replace each x in [l, r) by min(x, hi).
  void range_chmin(int l, int r, const T &hi) {
    check_range(l, r);
    if (l < r) {
      range_chmin_at(1, 0, n, l, r, hi);
    }
  }

  /// @brief Replace each x in [l, r) by max(x, lo).
  void range_chmax(int l, int r, const T &lo) {
    check_range(l, r);
    if (l < r) {
      range_chmax_at(1, 0, n, l, r, lo);
    }
  }

  /// @brief Return the sum over [l, r); an empty range has sum zero.
  T range_sum(int l, int r) {
    check_range(l, r);
    return l == r ? T{} : range_sum_at(1, 0, n, l, r);
  }

  /// @brief Return the minimum over the nonempty range [l, r).
  T range_min(int l, int r) {
    check_nonempty_range(l, r);
    return range_min_at(1, 0, n, l, r);
  }

  /// @brief Return the maximum over the nonempty range [l, r).
  T range_max(int l, int r) {
    check_nonempty_range(l, r);
    return range_max_at(1, 0, n, l, r);
  }

  /// @brief Return the sum of the entire array.
  T all_sum() const { return n == 0 ? T{} : tr[1].sum; }

  /// @brief Return the minimum of the nonempty array.
  T all_min() const {
    assert(n > 0);
    return tr[1].mn;
  }

  /// @brief Return the maximum of the nonempty array.
  T all_max() const {
    assert(n > 0);
    return tr[1].mx;
  }

private:
  void check_range(int l, int r) const { assert(0 <= l && l <= r && r <= n); }

  void check_nonempty_range(int l, int r) const {
    check_range(l, r);
    assert(l < r);
  }

  static node leaf(const T &x) {
    node res;
    res.sum = res.mx = res.mn = x;
    res.cmx = res.cmn = res.len = 1;
    return res;
  }

  static void assign_maximum(node &res, const node &l, const node &r) {
    if (l.mx == r.mx) {
      res.mx = l.mx;
      res.cmx = l.cmx + r.cmx;
      if (l.hmx && r.hmx) {
        res.mx2 = std::max(l.mx2, r.mx2);
        res.hmx = true;
      } else if (l.hmx) {
        res.mx2 = l.mx2;
        res.hmx = true;
      } else if (r.hmx) {
        res.mx2 = r.mx2;
        res.hmx = true;
      }
      return;
    }
    const node &hi = l.mx > r.mx ? l : r;
    const node &lo = l.mx > r.mx ? r : l;
    res.mx = hi.mx;
    res.cmx = hi.cmx;
    res.mx2 = hi.hmx ? std::max(hi.mx2, lo.mx) : lo.mx;
    res.hmx = true;
  }

  static void assign_minimum(node &res, const node &l, const node &r) {
    if (l.mn == r.mn) {
      res.mn = l.mn;
      res.cmn = l.cmn + r.cmn;
      if (l.hmn && r.hmn) {
        res.mn2 = std::min(l.mn2, r.mn2);
        res.hmn = true;
      } else if (l.hmn) {
        res.mn2 = l.mn2;
        res.hmn = true;
      } else if (r.hmn) {
        res.mn2 = r.mn2;
        res.hmn = true;
      }
      return;
    }
    const node &lo = l.mn < r.mn ? l : r;
    const node &hi = l.mn < r.mn ? r : l;
    res.mn = lo.mn;
    res.cmn = lo.cmn;
    res.mn2 = lo.hmn ? std::min(lo.mn2, hi.mn) : hi.mn;
    res.hmn = true;
  }

  static node merge_nodes(const node &l, const node &r) {
    node res;
    res.sum = l.sum + r.sum;
    res.len = l.len + r.len;
    assign_maximum(res, l, r);
    assign_minimum(res, l, r);
    return res;
  }

  void build_at(int id, int l, int r, const std::vector<T> &a) {
    if (r - l == 1) {
      tr[id] = leaf(a[l]);
      return;
    }
    int m = (l + r) / 2;
    build_at(id * 2, l, m, a);
    build_at(id * 2 + 1, m, r, a);
    pull(id);
  }

  void pull(int id) { tr[id] = merge_nodes(tr[id * 2], tr[id * 2 + 1]); }

  void apply_add(int id, const T &x) {
    node &u = tr[id];
    u.sum += x * u.len;
    u.mx += x;
    u.mn += x;
    if (u.hmx) {
      u.mx2 += x;
    }
    if (u.hmn) {
      u.mn2 += x;
    }
    u.add += x;
  }

  void apply_chmin(int id, const T &hi) {
    node &u = tr[id];
    if (u.mx <= hi) {
      return;
    }
    T old = u.mx;
    u.sum += (hi - old) * u.cmx;
    if (u.mn == old) {
      u.mn = hi;
    } else if (u.hmn && u.mn2 == old) {
      u.mn2 = hi;
    }
    u.mx = hi;
  }

  void apply_chmax(int id, const T &lo) {
    node &u = tr[id];
    if (lo <= u.mn) {
      return;
    }
    T old = u.mn;
    u.sum += (lo - old) * u.cmn;
    if (u.mx == old) {
      u.mx = lo;
    } else if (u.hmx && u.mx2 == old) {
      u.mx2 = lo;
    }
    u.mn = lo;
  }

  void push(int id) {
    node &u = tr[id];
    if (u.len == 1) {
      u.add = T{};
      return;
    }
    if (u.add != T{}) {
      apply_add(id * 2, u.add);
      apply_add(id * 2 + 1, u.add);
      u.add = T{};
    }
    if (tr[id * 2].mx > u.mx) {
      apply_chmin(id * 2, u.mx);
    }
    if (tr[id * 2 + 1].mx > u.mx) {
      apply_chmin(id * 2 + 1, u.mx);
    }
    if (tr[id * 2].mn < u.mn) {
      apply_chmax(id * 2, u.mn);
    }
    if (tr[id * 2 + 1].mn < u.mn) {
      apply_chmax(id * 2 + 1, u.mn);
    }
  }

  void range_add_at(int id, int l, int r, int ql, int qr, const T &x) {
    if (qr <= l || r <= ql) {
      return;
    }
    if (ql <= l && r <= qr) {
      apply_add(id, x);
      return;
    }
    push(id);
    int m = (l + r) / 2;
    range_add_at(id * 2, l, m, ql, qr, x);
    range_add_at(id * 2 + 1, m, r, ql, qr, x);
    pull(id);
  }

  void range_chmin_at(int id, int l, int r, int ql, int qr, const T &hi) {
    node &u = tr[id];
    if (qr <= l || r <= ql || u.mx <= hi) {
      return;
    }
    if (ql <= l && r <= qr && (!u.hmx || u.mx2 < hi)) {
      apply_chmin(id, hi);
      return;
    }
    push(id);
    int m = (l + r) / 2;
    range_chmin_at(id * 2, l, m, ql, qr, hi);
    range_chmin_at(id * 2 + 1, m, r, ql, qr, hi);
    pull(id);
  }

  void range_chmax_at(int id, int l, int r, int ql, int qr, const T &lo) {
    node &u = tr[id];
    if (qr <= l || r <= ql || lo <= u.mn) {
      return;
    }
    if (ql <= l && r <= qr && (!u.hmn || lo < u.mn2)) {
      apply_chmax(id, lo);
      return;
    }
    push(id);
    int m = (l + r) / 2;
    range_chmax_at(id * 2, l, m, ql, qr, lo);
    range_chmax_at(id * 2 + 1, m, r, ql, qr, lo);
    pull(id);
  }

  T range_sum_at(int id, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return tr[id].sum;
    }
    push(id);
    int m = (l + r) / 2;
    T res{};
    if (ql < m) {
      res += range_sum_at(id * 2, l, m, ql, qr);
    }
    if (m < qr) {
      res += range_sum_at(id * 2 + 1, m, r, ql, qr);
    }
    return res;
  }

  T range_min_at(int id, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return tr[id].mn;
    }
    push(id);
    int m = (l + r) / 2;
    T res = std::numeric_limits<T>::max();
    if (ql < m) {
      res = std::min(res, range_min_at(id * 2, l, m, ql, qr));
    }
    if (m < qr) {
      res = std::min(res, range_min_at(id * 2 + 1, m, r, ql, qr));
    }
    return res;
  }

  T range_max_at(int id, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return tr[id].mx;
    }
    push(id);
    int m = (l + r) / 2;
    T res = std::numeric_limits<T>::lowest();
    if (ql < m) {
      res = std::max(res, range_max_at(id * 2, l, m, ql, qr));
    }
    if (m < qr) {
      res = std::max(res, range_max_at(id * 2 + 1, m, r, ql, qr));
    }
    return res;
  }
};

} // namespace noya

#ifndef NOYA_SEGMENT_TREE_BEATS_HPP
#define NOYA_SEGMENT_TREE_BEATS_HPP 1

/// @complexity Time: O(n) build; amortized O(log^2 n) chmin/chmax and O(log n) add/query.
/// Space: O(n).

#include <algorithm>
#include <cassert>
#include <limits>
#include <vector>

namespace noya {

/// @brief Segment Tree Beats supporting range add, chmin, chmax, sum, minimum,
/// and maximum queries; bound updates run in amortized O(log^2 n) time.
template <class T> struct segment_tree_beats {
  struct node {
    // mx/mn: extrema; mx2/mn2: strict second extrema; cmx/cmn: multiplicities.
    T sum{};
    T mx{};
    T mx2{};
    T mn{};
    T mn2{};
    T add{};
    int cmx = 0;
    int cmn = 0;
    int len = 0;
    bool hmx = false;
    bool hmn = false;
  };

  int n = 0;
  std::vector<node> tr;

  segment_tree_beats() = default;
  explicit segment_tree_beats(const std::vector<T> &a) { build(a); }

  /// @brief Rebuild from array a in O(n) time.
  void build(const std::vector<T> &a) {
    n = int(a.size());
    tr.assign(std::max(1, 4 * n), {});
    if (n > 0) {
      build_at(1, 0, n, a);
    }
  }

  /// @brief Add x to every element of [l, r).
  void range_add(int l, int r, const T &x) {
    check_range(l, r);
    if (l < r) {
      range_add_at(1, 0, n, l, r, x);
    }
  }

  /// @brief Replace each x in [l, r) by min(x, hi).
  void range_chmin(int l, int r, const T &hi) {
    check_range(l, r);
    if (l < r) {
      range_chmin_at(1, 0, n, l, r, hi);
    }
  }

  /// @brief Replace each x in [l, r) by max(x, lo).
  void range_chmax(int l, int r, const T &lo) {
    check_range(l, r);
    if (l < r) {
      range_chmax_at(1, 0, n, l, r, lo);
    }
  }

  /// @brief Return the sum over [l, r); an empty range has sum zero.
  T range_sum(int l, int r) {
    check_range(l, r);
    return l == r ? T{} : range_sum_at(1, 0, n, l, r);
  }

  /// @brief Return the minimum over the nonempty range [l, r).
  T range_min(int l, int r) {
    check_nonempty_range(l, r);
    return range_min_at(1, 0, n, l, r);
  }

  /// @brief Return the maximum over the nonempty range [l, r).
  T range_max(int l, int r) {
    check_nonempty_range(l, r);
    return range_max_at(1, 0, n, l, r);
  }

  /// @brief Return the sum of the entire array.
  T all_sum() const { return n == 0 ? T{} : tr[1].sum; }

  /// @brief Return the minimum of the nonempty array.
  T all_min() const {
    assert(n > 0);
    return tr[1].mn;
  }

  /// @brief Return the maximum of the nonempty array.
  T all_max() const {
    assert(n > 0);
    return tr[1].mx;
  }

private:
  void check_range(int l, int r) const { assert(0 <= l && l <= r && r <= n); }

  void check_nonempty_range(int l, int r) const {
    check_range(l, r);
    assert(l < r);
  }

  static node leaf(const T &x) {
    node res;
    res.sum = res.mx = res.mn = x;
    res.cmx = res.cmn = res.len = 1;
    return res;
  }

  static void assign_maximum(node &res, const node &l, const node &r) {
    if (l.mx == r.mx) {
      res.mx = l.mx;
      res.cmx = l.cmx + r.cmx;
      if (l.hmx && r.hmx) {
        res.mx2 = std::max(l.mx2, r.mx2);
        res.hmx = true;
      } else if (l.hmx) {
        res.mx2 = l.mx2;
        res.hmx = true;
      } else if (r.hmx) {
        res.mx2 = r.mx2;
        res.hmx = true;
      }
      return;
    }
    const node &hi = l.mx > r.mx ? l : r;
    const node &lo = l.mx > r.mx ? r : l;
    res.mx = hi.mx;
    res.cmx = hi.cmx;
    res.mx2 = hi.hmx ? std::max(hi.mx2, lo.mx) : lo.mx;
    res.hmx = true;
  }

  static void assign_minimum(node &res, const node &l, const node &r) {
    if (l.mn == r.mn) {
      res.mn = l.mn;
      res.cmn = l.cmn + r.cmn;
      if (l.hmn && r.hmn) {
        res.mn2 = std::min(l.mn2, r.mn2);
        res.hmn = true;
      } else if (l.hmn) {
        res.mn2 = l.mn2;
        res.hmn = true;
      } else if (r.hmn) {
        res.mn2 = r.mn2;
        res.hmn = true;
      }
      return;
    }
    const node &lo = l.mn < r.mn ? l : r;
    const node &hi = l.mn < r.mn ? r : l;
    res.mn = lo.mn;
    res.cmn = lo.cmn;
    res.mn2 = lo.hmn ? std::min(lo.mn2, hi.mn) : hi.mn;
    res.hmn = true;
  }

  static node merge_nodes(const node &l, const node &r) {
    node res;
    res.sum = l.sum + r.sum;
    res.len = l.len + r.len;
    assign_maximum(res, l, r);
    assign_minimum(res, l, r);
    return res;
  }

  void build_at(int id, int l, int r, const std::vector<T> &a) {
    if (r - l == 1) {
      tr[id] = leaf(a[l]);
      return;
    }
    int m = (l + r) / 2;
    build_at(id * 2, l, m, a);
    build_at(id * 2 + 1, m, r, a);
    pull(id);
  }

  void pull(int id) { tr[id] = merge_nodes(tr[id * 2], tr[id * 2 + 1]); }

  void apply_add(int id, const T &x) {
    node &u = tr[id];
    u.sum += x * u.len;
    u.mx += x;
    u.mn += x;
    if (u.hmx) {
      u.mx2 += x;
    }
    if (u.hmn) {
      u.mn2 += x;
    }
    u.add += x;
  }

  void apply_chmin(int id, const T &hi) {
    node &u = tr[id];
    if (u.mx <= hi) {
      return;
    }
    T old = u.mx;
    u.sum += (hi - old) * u.cmx;
    if (u.mn == old) {
      u.mn = hi;
    } else if (u.hmn && u.mn2 == old) {
      u.mn2 = hi;
    }
    u.mx = hi;
  }

  void apply_chmax(int id, const T &lo) {
    node &u = tr[id];
    if (lo <= u.mn) {
      return;
    }
    T old = u.mn;
    u.sum += (lo - old) * u.cmn;
    if (u.mx == old) {
      u.mx = lo;
    } else if (u.hmx && u.mx2 == old) {
      u.mx2 = lo;
    }
    u.mn = lo;
  }

  void push(int id) {
    node &u = tr[id];
    if (u.len == 1) {
      u.add = T{};
      return;
    }
    if (u.add != T{}) {
      apply_add(id * 2, u.add);
      apply_add(id * 2 + 1, u.add);
      u.add = T{};
    }
    if (tr[id * 2].mx > u.mx) {
      apply_chmin(id * 2, u.mx);
    }
    if (tr[id * 2 + 1].mx > u.mx) {
      apply_chmin(id * 2 + 1, u.mx);
    }
    if (tr[id * 2].mn < u.mn) {
      apply_chmax(id * 2, u.mn);
    }
    if (tr[id * 2 + 1].mn < u.mn) {
      apply_chmax(id * 2 + 1, u.mn);
    }
  }

  void range_add_at(int id, int l, int r, int ql, int qr, const T &x) {
    if (qr <= l || r <= ql) {
      return;
    }
    if (ql <= l && r <= qr) {
      apply_add(id, x);
      return;
    }
    push(id);
    int m = (l + r) / 2;
    range_add_at(id * 2, l, m, ql, qr, x);
    range_add_at(id * 2 + 1, m, r, ql, qr, x);
    pull(id);
  }

  void range_chmin_at(int id, int l, int r, int ql, int qr, const T &hi) {
    node &u = tr[id];
    if (qr <= l || r <= ql || u.mx <= hi) {
      return;
    }
    if (ql <= l && r <= qr && (!u.hmx || u.mx2 < hi)) {
      apply_chmin(id, hi);
      return;
    }
    push(id);
    int m = (l + r) / 2;
    range_chmin_at(id * 2, l, m, ql, qr, hi);
    range_chmin_at(id * 2 + 1, m, r, ql, qr, hi);
    pull(id);
  }

  void range_chmax_at(int id, int l, int r, int ql, int qr, const T &lo) {
    node &u = tr[id];
    if (qr <= l || r <= ql || lo <= u.mn) {
      return;
    }
    if (ql <= l && r <= qr && (!u.hmn || lo < u.mn2)) {
      apply_chmax(id, lo);
      return;
    }
    push(id);
    int m = (l + r) / 2;
    range_chmax_at(id * 2, l, m, ql, qr, lo);
    range_chmax_at(id * 2 + 1, m, r, ql, qr, lo);
    pull(id);
  }

  T range_sum_at(int id, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return tr[id].sum;
    }
    push(id);
    int m = (l + r) / 2;
    T res{};
    if (ql < m) {
      res += range_sum_at(id * 2, l, m, ql, qr);
    }
    if (m < qr) {
      res += range_sum_at(id * 2 + 1, m, r, ql, qr);
    }
    return res;
  }

  T range_min_at(int id, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return tr[id].mn;
    }
    push(id);
    int m = (l + r) / 2;
    T res = std::numeric_limits<T>::max();
    if (ql < m) {
      res = std::min(res, range_min_at(id * 2, l, m, ql, qr));
    }
    if (m < qr) {
      res = std::min(res, range_min_at(id * 2 + 1, m, r, ql, qr));
    }
    return res;
  }

  T range_max_at(int id, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return tr[id].mx;
    }
    push(id);
    int m = (l + r) / 2;
    T res = std::numeric_limits<T>::lowest();
    if (ql < m) {
      res = std::max(res, range_max_at(id * 2, l, m, ql, qr));
    }
    if (m < qr) {
      res = std::max(res, range_max_at(id * 2 + 1, m, r, ql, qr));
    }
    return res;
  }
};

} // namespace noya

#endif // NOYA_SEGMENT_TREE_BEATS_HPP

#include <algorithm>
#include <cassert>
#include <limits>
#include <vector>

/// @complexity Time: O(n) build; amortized O(log^2 n) chmin/chmax and O(log n) add/query.
/// Space: O(n).

namespace noya {

/// @brief Segment Tree Beats supporting range add, chmin, chmax, sum, minimum,
/// and maximum queries; bound updates run in amortized O(log^2 n) time.
template <class T> struct segment_tree_beats {
  struct node {
    // mx/mn: extrema; mx2/mn2: strict second extrema; cmx/cmn: multiplicities.
    T sum{};
    T mx{};
    T mx2{};
    T mn{};
    T mn2{};
    T add{};
    int cmx = 0;
    int cmn = 0;
    int len = 0;
    bool hmx = false;
    bool hmn = false;
  };

  int n = 0;
  std::vector<node> tr;

  segment_tree_beats() = default;
  explicit segment_tree_beats(const std::vector<T> &a) { build(a); }

  /// @brief Rebuild from array a in O(n) time.
  void build(const std::vector<T> &a) {
    n = int(a.size());
    tr.assign(std::max(1, 4 * n), {});
    if (n > 0) {
      build_at(1, 0, n, a);
    }
  }

  /// @brief Add x to every element of [l, r).
  void range_add(int l, int r, const T &x) {
    check_range(l, r);
    if (l < r) {
      range_add_at(1, 0, n, l, r, x);
    }
  }

  /// @brief Replace each x in [l, r) by min(x, hi).
  void range_chmin(int l, int r, const T &hi) {
    check_range(l, r);
    if (l < r) {
      range_chmin_at(1, 0, n, l, r, hi);
    }
  }

  /// @brief Replace each x in [l, r) by max(x, lo).
  void range_chmax(int l, int r, const T &lo) {
    check_range(l, r);
    if (l < r) {
      range_chmax_at(1, 0, n, l, r, lo);
    }
  }

  /// @brief Return the sum over [l, r); an empty range has sum zero.
  T range_sum(int l, int r) {
    check_range(l, r);
    return l == r ? T{} : range_sum_at(1, 0, n, l, r);
  }

  /// @brief Return the minimum over the nonempty range [l, r).
  T range_min(int l, int r) {
    check_nonempty_range(l, r);
    return range_min_at(1, 0, n, l, r);
  }

  /// @brief Return the maximum over the nonempty range [l, r).
  T range_max(int l, int r) {
    check_nonempty_range(l, r);
    return range_max_at(1, 0, n, l, r);
  }

  /// @brief Return the sum of the entire array.
  T all_sum() const { return n == 0 ? T{} : tr[1].sum; }

  /// @brief Return the minimum of the nonempty array.
  T all_min() const {
    assert(n > 0);
    return tr[1].mn;
  }

  /// @brief Return the maximum of the nonempty array.
  T all_max() const {
    assert(n > 0);
    return tr[1].mx;
  }

private:
  void check_range(int l, int r) const { assert(0 <= l && l <= r && r <= n); }

  void check_nonempty_range(int l, int r) const {
    check_range(l, r);
    assert(l < r);
  }

  static node leaf(const T &x) {
    node res;
    res.sum = res.mx = res.mn = x;
    res.cmx = res.cmn = res.len = 1;
    return res;
  }

  static void assign_maximum(node &res, const node &l, const node &r) {
    if (l.mx == r.mx) {
      res.mx = l.mx;
      res.cmx = l.cmx + r.cmx;
      if (l.hmx && r.hmx) {
        res.mx2 = std::max(l.mx2, r.mx2);
        res.hmx = true;
      } else if (l.hmx) {
        res.mx2 = l.mx2;
        res.hmx = true;
      } else if (r.hmx) {
        res.mx2 = r.mx2;
        res.hmx = true;
      }
      return;
    }
    const node &hi = l.mx > r.mx ? l : r;
    const node &lo = l.mx > r.mx ? r : l;
    res.mx = hi.mx;
    res.cmx = hi.cmx;
    res.mx2 = hi.hmx ? std::max(hi.mx2, lo.mx) : lo.mx;
    res.hmx = true;
  }

  static void assign_minimum(node &res, const node &l, const node &r) {
    if (l.mn == r.mn) {
      res.mn = l.mn;
      res.cmn = l.cmn + r.cmn;
      if (l.hmn && r.hmn) {
        res.mn2 = std::min(l.mn2, r.mn2);
        res.hmn = true;
      } else if (l.hmn) {
        res.mn2 = l.mn2;
        res.hmn = true;
      } else if (r.hmn) {
        res.mn2 = r.mn2;
        res.hmn = true;
      }
      return;
    }
    const node &lo = l.mn < r.mn ? l : r;
    const node &hi = l.mn < r.mn ? r : l;
    res.mn = lo.mn;
    res.cmn = lo.cmn;
    res.mn2 = lo.hmn ? std::min(lo.mn2, hi.mn) : hi.mn;
    res.hmn = true;
  }

  static node merge_nodes(const node &l, const node &r) {
    node res;
    res.sum = l.sum + r.sum;
    res.len = l.len + r.len;
    assign_maximum(res, l, r);
    assign_minimum(res, l, r);
    return res;
  }

  void build_at(int id, int l, int r, const std::vector<T> &a) {
    if (r - l == 1) {
      tr[id] = leaf(a[l]);
      return;
    }
    int m = (l + r) / 2;
    build_at(id * 2, l, m, a);
    build_at(id * 2 + 1, m, r, a);
    pull(id);
  }

  void pull(int id) { tr[id] = merge_nodes(tr[id * 2], tr[id * 2 + 1]); }

  void apply_add(int id, const T &x) {
    node &u = tr[id];
    u.sum += x * u.len;
    u.mx += x;
    u.mn += x;
    if (u.hmx) {
      u.mx2 += x;
    }
    if (u.hmn) {
      u.mn2 += x;
    }
    u.add += x;
  }

  void apply_chmin(int id, const T &hi) {
    node &u = tr[id];
    if (u.mx <= hi) {
      return;
    }
    T old = u.mx;
    u.sum += (hi - old) * u.cmx;
    if (u.mn == old) {
      u.mn = hi;
    } else if (u.hmn && u.mn2 == old) {
      u.mn2 = hi;
    }
    u.mx = hi;
  }

  void apply_chmax(int id, const T &lo) {
    node &u = tr[id];
    if (lo <= u.mn) {
      return;
    }
    T old = u.mn;
    u.sum += (lo - old) * u.cmn;
    if (u.mx == old) {
      u.mx = lo;
    } else if (u.hmx && u.mx2 == old) {
      u.mx2 = lo;
    }
    u.mn = lo;
  }

  void push(int id) {
    node &u = tr[id];
    if (u.len == 1) {
      u.add = T{};
      return;
    }
    if (u.add != T{}) {
      apply_add(id * 2, u.add);
      apply_add(id * 2 + 1, u.add);
      u.add = T{};
    }
    if (tr[id * 2].mx > u.mx) {
      apply_chmin(id * 2, u.mx);
    }
    if (tr[id * 2 + 1].mx > u.mx) {
      apply_chmin(id * 2 + 1, u.mx);
    }
    if (tr[id * 2].mn < u.mn) {
      apply_chmax(id * 2, u.mn);
    }
    if (tr[id * 2 + 1].mn < u.mn) {
      apply_chmax(id * 2 + 1, u.mn);
    }
  }

  void range_add_at(int id, int l, int r, int ql, int qr, const T &x) {
    if (qr <= l || r <= ql) {
      return;
    }
    if (ql <= l && r <= qr) {
      apply_add(id, x);
      return;
    }
    push(id);
    int m = (l + r) / 2;
    range_add_at(id * 2, l, m, ql, qr, x);
    range_add_at(id * 2 + 1, m, r, ql, qr, x);
    pull(id);
  }

  void range_chmin_at(int id, int l, int r, int ql, int qr, const T &hi) {
    node &u = tr[id];
    if (qr <= l || r <= ql || u.mx <= hi) {
      return;
    }
    if (ql <= l && r <= qr && (!u.hmx || u.mx2 < hi)) {
      apply_chmin(id, hi);
      return;
    }
    push(id);
    int m = (l + r) / 2;
    range_chmin_at(id * 2, l, m, ql, qr, hi);
    range_chmin_at(id * 2 + 1, m, r, ql, qr, hi);
    pull(id);
  }

  void range_chmax_at(int id, int l, int r, int ql, int qr, const T &lo) {
    node &u = tr[id];
    if (qr <= l || r <= ql || lo <= u.mn) {
      return;
    }
    if (ql <= l && r <= qr && (!u.hmn || lo < u.mn2)) {
      apply_chmax(id, lo);
      return;
    }
    push(id);
    int m = (l + r) / 2;
    range_chmax_at(id * 2, l, m, ql, qr, lo);
    range_chmax_at(id * 2 + 1, m, r, ql, qr, lo);
    pull(id);
  }

  T range_sum_at(int id, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return tr[id].sum;
    }
    push(id);
    int m = (l + r) / 2;
    T res{};
    if (ql < m) {
      res += range_sum_at(id * 2, l, m, ql, qr);
    }
    if (m < qr) {
      res += range_sum_at(id * 2 + 1, m, r, ql, qr);
    }
    return res;
  }

  T range_min_at(int id, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return tr[id].mn;
    }
    push(id);
    int m = (l + r) / 2;
    T res = std::numeric_limits<T>::max();
    if (ql < m) {
      res = std::min(res, range_min_at(id * 2, l, m, ql, qr));
    }
    if (m < qr) {
      res = std::min(res, range_min_at(id * 2 + 1, m, r, ql, qr));
    }
    return res;
  }

  T range_max_at(int id, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return tr[id].mx;
    }
    push(id);
    int m = (l + r) / 2;
    T res = std::numeric_limits<T>::lowest();
    if (ql < m) {
      res = std::max(res, range_max_at(id * 2, l, m, ql, qr));
    }
    if (m < qr) {
      res = std::max(res, range_max_at(id * 2 + 1, m, r, ql, qr));
    }
    return res;
  }
};

} // namespace noya