ds/segtree/beats_summinmax_chminchmax.hpp

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

Depends on

• ds/segtree/segtree_beats.hpp

Verified with

• test/library_checker/datastructure/range_chmin_chmax_add_range_sum.test.cpp

Code

#include "ds/segtree/segtree_beats.hpp"


template <typename T>
struct Beats_SumMinMax_ChminChmax {
  struct SumMinMax {
    struct X {
      T sum, min, max, minc, maxc, min2, max2;
      bool fail;
    };
    using value_type = X;
    static X op(const X& x, const X& y) {
      if (x.min > x.max) return y;
      if (y.min > y.max) return x;
      X z;
      z.sum = x.sum + y.sum;

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

      z.min2 = z.max;
      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.max2 = z.min;
      if (z.max > x.max && x.max > z.max2) z.max2 = x.max;
      if (z.max > x.max2 && x.max2 > z.max2) z.max2 = x.max2;
      if (z.max > y.max && y.max > z.max2) z.max2 = y.max;
      if (z.max > y.max2 && y.max2 > z.max2) z.max2 = y.max2;

      z.fail = 0;
      return z;
    }
    static constexpr X unit() {
      return {0, infty<T>, -infty<T>, 0, 0, infty<T>, -infty<T>, 0};
    }
    bool commute = true;
  };
  struct AddChminChmax {
    using X = tuple<T, T, T>;
    using value_type = X;
    static constexpr X op(const X& x, const X& y) {
      auto [a, b, c] = x;
      auto [d, e, f] = y;
      a += d, b += d, c += d;
      b = min(b, e), c = min(c, e), c = max(c, f);
      return {a, b, c};
    }
    static constexpr X unit() { return {0, infty<T>, -infty<T>}; }
    bool commute = false;
  };
  struct Beats {
    using Monoid_X = SumMinMax;
    using Monoid_A = AddChminChmax;
    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 > x.max) return x;
      auto [add, mi, ma] = a;
      x.sum += cnt * add;
      x.min += add, x.max += add, x.min2 += add, x.max2 += add;

      if (mi == infty<T> && ma == -infty<T>) return x;

      T before_min = x.min, before_max = x.max;
      x.min = min(x.min, mi), x.min = max(x.min, ma);
      x.max = min(x.max, mi), x.max = max(x.max, ma);

      if (x.min == x.max) {
        x.sum = x.max * cnt, x.max2 = x.min2 = x.max, x.maxc = x.minc = cnt;
      }
      elif (x.max2 <= x.min) {
        x.max2 = x.min, x.min2 = x.max, x.minc = cnt - x.maxc,
        x.sum = x.max * x.maxc + x.min * x.minc;
      }
      elif (x.min2 >= x.max) {
        x.max2 = x.min, x.min2 = x.max, x.maxc = cnt - x.minc,
        x.sum = x.max * x.maxc + x.min * x.minc;
      }
      elif (x.min < x.min2 && x.max > x.max2) {
        x.sum += (x.min - before_min) * x.minc + (x.max - before_max) * x.maxc;
      }
      else {
        x.fail = 1;
      }
      return x;
    }
  };

  using X = typename SumMinMax::X;
  SegTree_Beats<Beats> seg;
  Beats_SumMinMax_ChminChmax(vc<T>& A) {
    seg.build(len(A), [&](int i) -> X { return from_element(A[i]); });
  }
  template <typename F>
  Beats_SumMinMax_ChminChmax(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, max, min)

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

  void chmin(int l, int r, T x) { seg.apply(l, r, {0, x, -infty<T>}); }
  void chmax(int l, int r, T x) { seg.apply(l, r, {0, infty<T>, x}); }
  void add(int l, int r, T x) { seg.apply(l, r, {x, infty<T>, -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_summinmax_chminchmax.hpp"

template <typename T>
struct Beats_SumMinMax_ChminChmax {
  struct SumMinMax {
    struct X {
      T sum, min, max, minc, maxc, min2, max2;
      bool fail;
    };
    using value_type = X;
    static X op(const X& x, const X& y) {
      if (x.min > x.max) return y;
      if (y.min > y.max) return x;
      X z;
      z.sum = x.sum + y.sum;

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

      z.min2 = z.max;
      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.max2 = z.min;
      if (z.max > x.max && x.max > z.max2) z.max2 = x.max;
      if (z.max > x.max2 && x.max2 > z.max2) z.max2 = x.max2;
      if (z.max > y.max && y.max > z.max2) z.max2 = y.max;
      if (z.max > y.max2 && y.max2 > z.max2) z.max2 = y.max2;

      z.fail = 0;
      return z;
    }
    static constexpr X unit() {
      return {0, infty<T>, -infty<T>, 0, 0, infty<T>, -infty<T>, 0};
    }
    bool commute = true;
  };
  struct AddChminChmax {
    using X = tuple<T, T, T>;
    using value_type = X;
    static constexpr X op(const X& x, const X& y) {
      auto [a, b, c] = x;
      auto [d, e, f] = y;
      a += d, b += d, c += d;
      b = min(b, e), c = min(c, e), c = max(c, f);
      return {a, b, c};
    }
    static constexpr X unit() { return {0, infty<T>, -infty<T>}; }
    bool commute = false;
  };
  struct Beats {
    using Monoid_X = SumMinMax;
    using Monoid_A = AddChminChmax;
    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 > x.max) return x;
      auto [add, mi, ma] = a;
      x.sum += cnt * add;
      x.min += add, x.max += add, x.min2 += add, x.max2 += add;

      if (mi == infty<T> && ma == -infty<T>) return x;

      T before_min = x.min, before_max = x.max;
      x.min = min(x.min, mi), x.min = max(x.min, ma);
      x.max = min(x.max, mi), x.max = max(x.max, ma);

      if (x.min == x.max) {
        x.sum = x.max * cnt, x.max2 = x.min2 = x.max, x.maxc = x.minc = cnt;
      }
      elif (x.max2 <= x.min) {
        x.max2 = x.min, x.min2 = x.max, x.minc = cnt - x.maxc,
        x.sum = x.max * x.maxc + x.min * x.minc;
      }
      elif (x.min2 >= x.max) {
        x.max2 = x.min, x.min2 = x.max, x.maxc = cnt - x.minc,
        x.sum = x.max * x.maxc + x.min * x.minc;
      }
      elif (x.min < x.min2 && x.max > x.max2) {
        x.sum += (x.min - before_min) * x.minc + (x.max - before_max) * x.maxc;
      }
      else {
        x.fail = 1;
      }
      return x;
    }
  };

  using X = typename SumMinMax::X;
  SegTree_Beats<Beats> seg;
  Beats_SumMinMax_ChminChmax(vc<T>& A) {
    seg.build(len(A), [&](int i) -> X { return from_element(A[i]); });
  }
  template <typename F>
  Beats_SumMinMax_ChminChmax(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, max, min)

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

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

Back to top page