ds/segtree/beats_summin_chmax.hpp

• View this file on GitHub
• Last update: 2023-02-01 23:31:55+09:00
• Include: #include "ds/segtree/beats_summin_chmax.hpp"

Depends on

• ds/segtree/segtree_beats.hpp

Verified with

• test/3_yukicoder/1526.test.cpp

Code

#include "ds/segtree/segtree_beats.hpp"
template <typename T>
struct Beats_SumMin_Chmax {
  struct SumMin {
    struct X {
      T sum, min, minc, min2;
      bool fail;
    };
    using value_type = X;
    static X op(const X& x, const X& y) {
      if (x.min == infty<T>) return y;
      if (y.min == infty<T>) return x;
      X z;
      z.sum = x.sum + y.sum;

      z.min = min(x.min, y.min);
      z.minc = (x.min == z.min ? x.minc : 0) + (y.min == z.min ? y.minc : 0);

      z.min2 = infty<T>;
      if (z.min < x.min && x.min < z.min2) z.min2 = x.min;
      if (z.min < x.min2 && x.min2 < z.min2) z.min2 = x.min2;
      if (z.min < y.min && y.min < z.min2) z.min2 = y.min;
      if (z.min < y.min2 && y.min2 < z.min2) z.min2 = y.min2;

      z.fail = 0;
      return z;
    }
    static constexpr X unit() { return {0, infty<T>, 0, infty<T>, 0}; }
    bool commute = true;
  };
  struct AddChmax {
    using X = pair<T, T>;
    using value_type = X;
    static constexpr X op(const X& x, const X& y) {
      auto [a, c] = x;
      auto [d, f] = y;
      a += d, c += d, c = max(c, f);
      return {a, c};
    }
    static constexpr X unit() { return {0, -infty<T>}; }
    bool commute = false;
  };
  struct Beats {
    using Monoid_X = SumMin;
    using Monoid_A = AddChmax;
    using X = typename Monoid_X::value_type;
    using A = typename Monoid_A::value_type;
    static X act(X& x, const A& a, int cnt) {
      assert(!x.fail);
      if (x.min == infty<T>) return x;
      auto [add, ma] = a;
      x.sum += cnt * add, x.min += add, x.min2 += add;
      if (ma == -infty<T>) return x;

      T before_min = x.min;
      x.min = max(x.min, ma);
      if (x.minc == cnt) { x.min2 = x.min, x.sum = cnt * x.min; }
      elif (x.min2 > x.min) { x.sum += (x.min - before_min) * x.minc; }
      else {
        x.fail = 1;
      }
      return x;
    }
  };
  using X = typename SumMin::X;
  SegTree_Beats<Beats> seg;
  Beats_SumMin_Chmax(vc<T>& A) {
    seg.build(len(A), [&](int i) -> X { return from_element(A[i]); });
  }
  template <typename F>
  Beats_SumMin_Chmax(int n, F f) {
    seg.build(n, [&](int i) -> X { return from_element(f(i)); });
  }
  void set(int i, T x) { seg.set(i, from_element(x)); }

  // (sum, min)
  pair<T, T> prod(int l, int r) {
    auto e = seg.prod(l, r);
    return {e.sum, e.min};
  }
  static X from_element(T x) { return {x, x, 1, x}; }

  void chmax(int l, int r, T x) { seg.apply(l, r, {0, x}); }
  void add(int l, int r, T x) { seg.apply(l, r, {x, -infty<T>}); }
};

#line 2 "ds/segtree/segtree_beats.hpp"

template <typename ActedMonoid>
struct SegTree_Beats {
  using AM = ActedMonoid;
  using MX = typename AM::Monoid_X;
  using MA = typename AM::Monoid_A;
  using X = typename MX::value_type;
  using A = typename MA::value_type;
  int n, log, size;
  vc<X> dat;
  vc<A> laz;

  SegTree_Beats() {}
  SegTree_Beats(int n) { build(n); }
  template <typename F>
  SegTree_Beats(int n, F f) {
    build(n, f);
  }
  SegTree_Beats(const vc<X>& v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> X { return MX::unit(); });
  }
  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m, log = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, MX::unit());
    laz.assign(size, MA::unit());
    FOR(i, n) dat[size + i] = f(i);
    FOR_R(i, 1, size) update(i);
  }

  void update(int k) { dat[k] = MX::op(dat[2 * k], dat[2 * k + 1]); }
  void set(int p, X x) {
    assert(0 <= p && p < n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    dat[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }

  X get(int p) {
    assert(0 <= p && p < n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    return dat[p];
  }

  /*
  void all_apply(int k, A a) {
    dat[k] = ActedMonoid::act(dat[k], a);
    if (k < size) {
      laz[k] = MA::op(laz[k], a);
      if (dat[k].fail) push(k), update(k);
    }
  }
  */

  vc<X> get_all() {
    FOR(k, 1, size) { push(k); }
    return {dat.begin() + size, dat.begin() + size + n};
  }

  X prod(int l, int r) {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) return MX::unit();
    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);
    }
    X xl = MX::unit(), xr = MX::unit();
    while (l < r) {
      if (l & 1) xl = MX::op(xl, dat[l++]);
      if (r & 1) xr = MX::op(dat[--r], xr);
      l >>= 1, r >>= 1;
    }
    return MX::op(xl, xr);
  }

  X prod_all() { return dat[1]; }

  void apply(int l, int r, A a) {
    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) apply_at(l++, a);
      if (r & 1) apply_at(--r, a);
      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);
    }
  }

private:
  void apply_at(int k, A a) {
    int sz = 1 << (log - topbit(k));
    dat[k] = AM::act(dat[k], a, sz);
    if (k < size) {
      laz[k] = MA::op(laz[k], a);
      if (dat[k].fail) push(k), update(k);
    }
  }

  void push(int k) {
    if (laz[k] == MA::unit()) return;
    apply_at(2 * k, laz[k]), apply_at(2 * k + 1, laz[k]);
    laz[k] = MA::unit();
  }
};
#line 2 "ds/segtree/beats_summin_chmax.hpp"
template <typename T>
struct Beats_SumMin_Chmax {
  struct SumMin {
    struct X {
      T sum, min, minc, min2;
      bool fail;
    };
    using value_type = X;
    static X op(const X& x, const X& y) {
      if (x.min == infty<T>) return y;
      if (y.min == infty<T>) return x;
      X z;
      z.sum = x.sum + y.sum;

      z.min = min(x.min, y.min);
      z.minc = (x.min == z.min ? x.minc : 0) + (y.min == z.min ? y.minc : 0);

      z.min2 = infty<T>;
      if (z.min < x.min && x.min < z.min2) z.min2 = x.min;
      if (z.min < x.min2 && x.min2 < z.min2) z.min2 = x.min2;
      if (z.min < y.min && y.min < z.min2) z.min2 = y.min;
      if (z.min < y.min2 && y.min2 < z.min2) z.min2 = y.min2;

      z.fail = 0;
      return z;
    }
    static constexpr X unit() { return {0, infty<T>, 0, infty<T>, 0}; }
    bool commute = true;
  };
  struct AddChmax {
    using X = pair<T, T>;
    using value_type = X;
    static constexpr X op(const X& x, const X& y) {
      auto [a, c] = x;
      auto [d, f] = y;
      a += d, c += d, c = max(c, f);
      return {a, c};
    }
    static constexpr X unit() { return {0, -infty<T>}; }
    bool commute = false;
  };
  struct Beats {
    using Monoid_X = SumMin;
    using Monoid_A = AddChmax;
    using X = typename Monoid_X::value_type;
    using A = typename Monoid_A::value_type;
    static X act(X& x, const A& a, int cnt) {
      assert(!x.fail);
      if (x.min == infty<T>) return x;
      auto [add, ma] = a;
      x.sum += cnt * add, x.min += add, x.min2 += add;
      if (ma == -infty<T>) return x;

      T before_min = x.min;
      x.min = max(x.min, ma);
      if (x.minc == cnt) { x.min2 = x.min, x.sum = cnt * x.min; }
      elif (x.min2 > x.min) { x.sum += (x.min - before_min) * x.minc; }
      else {
        x.fail = 1;
      }
      return x;
    }
  };
  using X = typename SumMin::X;
  SegTree_Beats<Beats> seg;
  Beats_SumMin_Chmax(vc<T>& A) {
    seg.build(len(A), [&](int i) -> X { return from_element(A[i]); });
  }
  template <typename F>
  Beats_SumMin_Chmax(int n, F f) {
    seg.build(n, [&](int i) -> X { return from_element(f(i)); });
  }
  void set(int i, T x) { seg.set(i, from_element(x)); }

  // (sum, min)
  pair<T, T> prod(int l, int r) {
    auto e = seg.prod(l, r);
    return {e.sum, e.min};
  }
  static X from_element(T x) { return {x, x, 1, x}; }

  void chmax(int l, int r, T x) { seg.apply(l, r, {0, x}); }
  void add(int l, int r, T x) { seg.apply(l, r, {x, -infty<T>}); }
};

Back to top page