tools/preset_segtree_beats.hpp

• View this file on GitHub
• Last update: 2024-08-20 21:27:11+09:00
• Include: #include "tools/preset_segtree_beats.hpp"
• Link: https://github.com/hitonanode/cplib-cpp/blob/5dc514109dcc62c00c9b96b044b0e57d76ac7e9b/segmenttree/acl_beats.hpp

Depends on

• tools/segtree_beats.hpp

Verified with

• tests/preset_segtree_beats.test.cpp

Code

#ifndef TOOLS_PRESET_SEGTREE_BEATS_HPP
#define TOOLS_PRESET_SEGTREE_BEATS_HPP

#include <cassert>
#include <algorithm>
#include <limits>
#include <vector>
#include "tools/segtree_beats.hpp"

// Source: https://github.com/hitonanode/cplib-cpp/blob/5dc514109dcc62c00c9b96b044b0e57d76ac7e9b/segmenttree/acl_beats.hpp
// License: MIT
// Author: hitonanode

// MIT License
// 
// Copyright (c) 2019 Ryotaro Sato
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

namespace tools {
  namespace detail {
    namespace preset_segtree_beats {
      template <typename T>
      T second_lowest(const T a, const T a2, const T c, const T c2) {
        assert(a <= a2); // a < a2 or a == a2 == INF
        assert(c <= c2); // c < c2 or c == c2 == -INF
        return a == c ? ::std::min(a2, c2) : a2 <= c ? a2 : c2 <= a ? c2 : ::std::max(a, c);
      }

      template <typename T>
      T second_highest(const T a, const T a2, const T b, const T b2) {
        assert(a >= a2); // a > a2 or a == a2 == -INF
        assert(b >= b2); // b > b2 or b == b2 == INF
        return a == b ? ::std::max(a2, b2) : a2 >= b ? a2 : b2 >= a ? b2 : ::std::min(a, b);
      }

      template <typename T>
      struct S {
        T lo, hi, lo2, hi2, sum, sz, nlo, nhi;
        bool fail;
        S():
          lo(::std::numeric_limits<T>::max()),
          hi(::std::numeric_limits<T>::min()),
          lo2(::std::numeric_limits<T>::max()),
          hi2(::std::numeric_limits<T>::min()),
          sum(0),
          sz(0),
          nlo(0),
          nhi(0),
          fail(false) {
        }
        S(const T x, const T sz_):
          lo(x),
          hi(x),
          lo2(::std::numeric_limits<T>::max()),
          hi2(::std::numeric_limits<T>::min()),
          sum(x * sz_),
          sz(sz_),
          nlo(sz_),
          nhi(sz_),
          fail(false) {
        }
      };

      template <typename T>
      S<T> op(const S<T>& l, const S<T>& r) {
        if (l.lo > l.hi) return r;
        if (r.lo > r.hi) return l;
        S<T> ret;
        ret.lo = ::std::min(l.lo, r.lo);
        ret.hi = ::std::max(l.hi, r.hi);
        ret.lo2 = second_lowest(l.lo, l.lo2, r.lo, r.lo2);
        ret.hi2 = second_highest(l.hi, l.hi2, r.hi, r.hi2);
        ret.sum = l.sum + r.sum;
        ret.sz = l.sz + r.sz;
        ret.nlo = l.nlo * (l.lo <= r.lo) + r.nlo * (r.lo <= l.lo);
        ret.nhi = l.nhi * (l.hi >= r.hi) + r.nhi * (r.hi >= l.hi);
        return ret;
      }

      template <typename T>
      S<T> e() {
        return S<T>();
      }

      template <typename T>
      struct F {
        T lb, ub, bias;
        F():
          lb(::std::numeric_limits<T>::min()),
          ub(::std::numeric_limits<T>::max()),
          bias(0) {
        }
        F(const T chmax_, const T chmin_, const T add):
          lb(chmax_),
          ub(chmin_),
          bias(add) {
        }
        static F<T> chmin(const T x) {
          return F<T>(::std::numeric_limits<T>::min(), x, 0);
        }
        static F<T> chmax(const T x) {
          return F<T>(x, ::std::numeric_limits<T>::max(), 0);
        }
        static F<T> add(const T x) {
          return F<T>(::std::numeric_limits<T>::min(), ::std::numeric_limits<T>::max(), x);
        }
      };

      template <typename T>
      S<T> mapping(const F<T>& f, S<T> x) {
        if (x.sz == 0) return e<T>();

        // f の作用後 x の要素が 1 種類だけになるケース
        if (x.lo == x.hi || f.lb == f.ub || f.lb >= x.hi || f.ub <= x.lo) {
          return S<T>(::std::clamp(x.lo, f.lb, f.ub) + f.bias, x.sz);
        }

        // 2 種類 -> 1 種類
        if (x.lo2 == x.hi) {
          x.lo = x.hi2 = ::std::max(x.lo, f.lb) + f.bias;
          x.hi = x.lo2 = ::std::min(x.hi, f.ub) + f.bias;
          x.sum = x.lo * x.nlo + x.hi * x.nhi;
          return x;
        }

        // lo と lo2, hi と hi2 が潰れないケース
        if (f.lb < x.lo2 && f.ub > x.hi2) {
          T nxt_lo = std::max(x.lo, f.lb);
          T nxt_hi = std::min(x.hi, f.ub);
          x.sum += (nxt_lo - x.lo) * x.nlo - (x.hi - nxt_hi) * x.nhi + f.bias * x.sz;
          x.lo = nxt_lo + f.bias;
          x.hi = nxt_hi + f.bias;
          x.lo2 += f.bias;
          x.hi2 += f.bias;
          return x;
        }

        x.fail = true;
        return x;
      }

      template <typename T>
      F<T> composition(const F<T>& fnew, const F<T>& fold) {
        F<T> ret;

        ret.lb = fold.lb;
        if (::std::numeric_limits<T>::min() < ret.lb && ret.lb < ::std::numeric_limits<T>::max()) ret.lb += fold.bias;
        ret.lb = ::std::clamp(ret.lb, fnew.lb, fnew.ub);
        if (::std::numeric_limits<T>::min() < ret.lb && ret.lb < ::std::numeric_limits<T>::max()) ret.lb -= fold.bias;

        ret.ub = fold.ub;
        if (::std::numeric_limits<T>::min() < ret.ub && ret.ub < ::std::numeric_limits<T>::max()) ret.ub += fold.bias;
        ret.ub = ::std::clamp(ret.ub, fnew.lb, fnew.ub);
        if (::std::numeric_limits<T>::min() < ret.ub && ret.ub < ::std::numeric_limits<T>::max()) ret.ub -= fold.bias;

        ret.bias = fold.bias + fnew.bias;

        return ret;
      }

      template <typename T>
      F<T> id() {
        return F<T>();
      }

      template <typename T>
      using Base = ::tools::segtree_beats<S<T>, op<T>, e<T>, F<T>, mapping<T>, composition<T>, id<T>>;
    }
  }

  template <typename T>
  class preset_segtree_beats {
  private:
    ::tools::detail::preset_segtree_beats::Base<T> m_base;
    using S = ::tools::detail::preset_segtree_beats::S<T>;
    using F = ::tools::detail::preset_segtree_beats::F<T>;

  public:
    preset_segtree_beats(const ::tools::preset_segtree_beats<T>&) = default;
    preset_segtree_beats(::tools::preset_segtree_beats<T>&&) = default;
    ~preset_segtree_beats() = default;
    ::tools::preset_segtree_beats<T>& operator=(const ::tools::preset_segtree_beats<T>&) = default;
    ::tools::preset_segtree_beats<T>& operator=(::tools::preset_segtree_beats<T>&&) = default;

    explicit preset_segtree_beats(const int n) : m_base(n) {
    }
    template <typename InputIterator>
    preset_segtree_beats(const InputIterator begin, const InputIterator end) : m_base([&]() {
      ::std::vector<S> v;
      for (auto it = begin; it != end; ++it) {
        v.emplace_back(*it, 1);
      }
      return v;
    }()) {
    }
    explicit preset_segtree_beats(const ::std::vector<T>& v) : preset_segtree_beats(v.begin(), v.end()) {
    }

    void set(const int p, const T x) {
      this->m_base.set(p, S(x, 1));
    }
    T get(const int p) {
      return this->m_base.get(p).sum;
    }
    T min(const int l, const int r) {
      return this->m_base.prod(l, r).lo;
    }
    T max(const int l, const int r) {
      return this->m_base.prod(l, r).hi;
    }
    T sum(const int l, const int r) {
      return this->m_base.prod(l, r).sum;
    }
    T all_min() {
      return this->m_base.all_prod().lo;
    }
    T all_max() {
      return this->m_base.all_prod().hi;
    }
    T all_sum() {
      return this->m_base.all_prod().sum;
    }
    void chmin(const int p, const T f) {
      this->m_base.apply(p, F::chmin(f));
    }
    void chmax(const int p, const T f) {
      this->m_base.apply(p, F::chmax(f));
    }
    void add(const int p, const T f) {
      this->m_base.apply(p, F::add(f));
    }
    void chmin(const int l, const int r, const T f) {
      this->m_base.apply(l, r, F::chmin(f));
    }
    void chmax(const int l, const int r, const T f) {
      this->m_base.apply(l, r, F::chmax(f));
    }
    void add(const int l, const int r, const T f) {
      this->m_base.apply(l, r, F::add(f));
    }
    template <class G>
    int max_right(const int l, const G g) {
      return this->m_base.max_right(l, g);
    }
    template <class G>
    int min_left(const int r, const G g) {
      return this->m_base.min_left(r, g);
    }
  };
}

#endif

#line 1 "tools/preset_segtree_beats.hpp"



#include <cassert>
#include <algorithm>
#include <limits>
#include <vector>
#line 1 "tools/segtree_beats.hpp"



#line 1 "lib/ac-library/atcoder/lazysegtree.hpp"



#line 6 "lib/ac-library/atcoder/lazysegtree.hpp"
#include <functional>
#line 8 "lib/ac-library/atcoder/lazysegtree.hpp"

#line 1 "lib/ac-library/atcoder/internal_bit.hpp"



#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder


#line 10 "lib/ac-library/atcoder/lazysegtree.hpp"

namespace atcoder {

#if __cplusplus >= 201703L

template <class S,
          auto op,
          auto e,
          class F,
          auto mapping,
          auto composition,
          auto id>
struct lazy_segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");
    static_assert(
        std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
        "mapping must work as F(F, S)");
    static_assert(
        std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
        "compostiion must work as F(F, F)");
    static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
                  "id must work as F()");

#else

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {

#endif

  public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S 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);
    }

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

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return 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);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S 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] = 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)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

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

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

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

}  // namespace atcoder


#line 5 "tools/segtree_beats.hpp"

// Source: https://github.com/hitonanode/cplib-cpp/blob/94a544f88242fec39b4dd434ed379c23aa4dd99b/segmenttree/acl_beats.hpp
// License: MIT
// Author: hitonanode

// MIT License
// 
// Copyright (c) 2019 Ryotaro Sato
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

namespace tools {
  template <class S, auto op, auto e, class F, auto mapping, auto composition, auto id>
  class segtree_beats : public ::atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> {
    using Base = ::atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
    using Base::lazy_segtree;
    void all_apply(int k, F f) override {
      Base::d[k] = mapping(f, Base::d[k]);
      if (k < Base::size) {
        Base::lz[k] = composition(f, Base::lz[k]);
        if (Base::d[k].fail) Base::push(k), Base::update(k);
      }
    }
  };
}


#line 9 "tools/preset_segtree_beats.hpp"

// Source: https://github.com/hitonanode/cplib-cpp/blob/5dc514109dcc62c00c9b96b044b0e57d76ac7e9b/segmenttree/acl_beats.hpp
// License: MIT
// Author: hitonanode

// MIT License
// 
// Copyright (c) 2019 Ryotaro Sato
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

namespace tools {
  namespace detail {
    namespace preset_segtree_beats {
      template <typename T>
      T second_lowest(const T a, const T a2, const T c, const T c2) {
        assert(a <= a2); // a < a2 or a == a2 == INF
        assert(c <= c2); // c < c2 or c == c2 == -INF
        return a == c ? ::std::min(a2, c2) : a2 <= c ? a2 : c2 <= a ? c2 : ::std::max(a, c);
      }

      template <typename T>
      T second_highest(const T a, const T a2, const T b, const T b2) {
        assert(a >= a2); // a > a2 or a == a2 == -INF
        assert(b >= b2); // b > b2 or b == b2 == INF
        return a == b ? ::std::max(a2, b2) : a2 >= b ? a2 : b2 >= a ? b2 : ::std::min(a, b);
      }

      template <typename T>
      struct S {
        T lo, hi, lo2, hi2, sum, sz, nlo, nhi;
        bool fail;
        S():
          lo(::std::numeric_limits<T>::max()),
          hi(::std::numeric_limits<T>::min()),
          lo2(::std::numeric_limits<T>::max()),
          hi2(::std::numeric_limits<T>::min()),
          sum(0),
          sz(0),
          nlo(0),
          nhi(0),
          fail(false) {
        }
        S(const T x, const T sz_):
          lo(x),
          hi(x),
          lo2(::std::numeric_limits<T>::max()),
          hi2(::std::numeric_limits<T>::min()),
          sum(x * sz_),
          sz(sz_),
          nlo(sz_),
          nhi(sz_),
          fail(false) {
        }
      };

      template <typename T>
      S<T> op(const S<T>& l, const S<T>& r) {
        if (l.lo > l.hi) return r;
        if (r.lo > r.hi) return l;
        S<T> ret;
        ret.lo = ::std::min(l.lo, r.lo);
        ret.hi = ::std::max(l.hi, r.hi);
        ret.lo2 = second_lowest(l.lo, l.lo2, r.lo, r.lo2);
        ret.hi2 = second_highest(l.hi, l.hi2, r.hi, r.hi2);
        ret.sum = l.sum + r.sum;
        ret.sz = l.sz + r.sz;
        ret.nlo = l.nlo * (l.lo <= r.lo) + r.nlo * (r.lo <= l.lo);
        ret.nhi = l.nhi * (l.hi >= r.hi) + r.nhi * (r.hi >= l.hi);
        return ret;
      }

      template <typename T>
      S<T> e() {
        return S<T>();
      }

      template <typename T>
      struct F {
        T lb, ub, bias;
        F():
          lb(::std::numeric_limits<T>::min()),
          ub(::std::numeric_limits<T>::max()),
          bias(0) {
        }
        F(const T chmax_, const T chmin_, const T add):
          lb(chmax_),
          ub(chmin_),
          bias(add) {
        }
        static F<T> chmin(const T x) {
          return F<T>(::std::numeric_limits<T>::min(), x, 0);
        }
        static F<T> chmax(const T x) {
          return F<T>(x, ::std::numeric_limits<T>::max(), 0);
        }
        static F<T> add(const T x) {
          return F<T>(::std::numeric_limits<T>::min(), ::std::numeric_limits<T>::max(), x);
        }
      };

      template <typename T>
      S<T> mapping(const F<T>& f, S<T> x) {
        if (x.sz == 0) return e<T>();

        // f の作用後 x の要素が 1 種類だけになるケース
        if (x.lo == x.hi || f.lb == f.ub || f.lb >= x.hi || f.ub <= x.lo) {
          return S<T>(::std::clamp(x.lo, f.lb, f.ub) + f.bias, x.sz);
        }

        // 2 種類 -> 1 種類
        if (x.lo2 == x.hi) {
          x.lo = x.hi2 = ::std::max(x.lo, f.lb) + f.bias;
          x.hi = x.lo2 = ::std::min(x.hi, f.ub) + f.bias;
          x.sum = x.lo * x.nlo + x.hi * x.nhi;
          return x;
        }

        // lo と lo2, hi と hi2 が潰れないケース
        if (f.lb < x.lo2 && f.ub > x.hi2) {
          T nxt_lo = std::max(x.lo, f.lb);
          T nxt_hi = std::min(x.hi, f.ub);
          x.sum += (nxt_lo - x.lo) * x.nlo - (x.hi - nxt_hi) * x.nhi + f.bias * x.sz;
          x.lo = nxt_lo + f.bias;
          x.hi = nxt_hi + f.bias;
          x.lo2 += f.bias;
          x.hi2 += f.bias;
          return x;
        }

        x.fail = true;
        return x;
      }

      template <typename T>
      F<T> composition(const F<T>& fnew, const F<T>& fold) {
        F<T> ret;

        ret.lb = fold.lb;
        if (::std::numeric_limits<T>::min() < ret.lb && ret.lb < ::std::numeric_limits<T>::max()) ret.lb += fold.bias;
        ret.lb = ::std::clamp(ret.lb, fnew.lb, fnew.ub);
        if (::std::numeric_limits<T>::min() < ret.lb && ret.lb < ::std::numeric_limits<T>::max()) ret.lb -= fold.bias;

        ret.ub = fold.ub;
        if (::std::numeric_limits<T>::min() < ret.ub && ret.ub < ::std::numeric_limits<T>::max()) ret.ub += fold.bias;
        ret.ub = ::std::clamp(ret.ub, fnew.lb, fnew.ub);
        if (::std::numeric_limits<T>::min() < ret.ub && ret.ub < ::std::numeric_limits<T>::max()) ret.ub -= fold.bias;

        ret.bias = fold.bias + fnew.bias;

        return ret;
      }

      template <typename T>
      F<T> id() {
        return F<T>();
      }

      template <typename T>
      using Base = ::tools::segtree_beats<S<T>, op<T>, e<T>, F<T>, mapping<T>, composition<T>, id<T>>;
    }
  }

  template <typename T>
  class preset_segtree_beats {
  private:
    ::tools::detail::preset_segtree_beats::Base<T> m_base;
    using S = ::tools::detail::preset_segtree_beats::S<T>;
    using F = ::tools::detail::preset_segtree_beats::F<T>;

  public:
    preset_segtree_beats(const ::tools::preset_segtree_beats<T>&) = default;
    preset_segtree_beats(::tools::preset_segtree_beats<T>&&) = default;
    ~preset_segtree_beats() = default;
    ::tools::preset_segtree_beats<T>& operator=(const ::tools::preset_segtree_beats<T>&) = default;
    ::tools::preset_segtree_beats<T>& operator=(::tools::preset_segtree_beats<T>&&) = default;

    explicit preset_segtree_beats(const int n) : m_base(n) {
    }
    template <typename InputIterator>
    preset_segtree_beats(const InputIterator begin, const InputIterator end) : m_base([&]() {
      ::std::vector<S> v;
      for (auto it = begin; it != end; ++it) {
        v.emplace_back(*it, 1);
      }
      return v;
    }()) {
    }
    explicit preset_segtree_beats(const ::std::vector<T>& v) : preset_segtree_beats(v.begin(), v.end()) {
    }

    void set(const int p, const T x) {
      this->m_base.set(p, S(x, 1));
    }
    T get(const int p) {
      return this->m_base.get(p).sum;
    }
    T min(const int l, const int r) {
      return this->m_base.prod(l, r).lo;
    }
    T max(const int l, const int r) {
      return this->m_base.prod(l, r).hi;
    }
    T sum(const int l, const int r) {
      return this->m_base.prod(l, r).sum;
    }
    T all_min() {
      return this->m_base.all_prod().lo;
    }
    T all_max() {
      return this->m_base.all_prod().hi;
    }
    T all_sum() {
      return this->m_base.all_prod().sum;
    }
    void chmin(const int p, const T f) {
      this->m_base.apply(p, F::chmin(f));
    }
    void chmax(const int p, const T f) {
      this->m_base.apply(p, F::chmax(f));
    }
    void add(const int p, const T f) {
      this->m_base.apply(p, F::add(f));
    }
    void chmin(const int l, const int r, const T f) {
      this->m_base.apply(l, r, F::chmin(f));
    }
    void chmax(const int l, const int r, const T f) {
      this->m_base.apply(l, r, F::chmax(f));
    }
    void add(const int l, const int r, const T f) {
      this->m_base.apply(l, r, F::add(f));
    }
    template <class G>
    int max_right(const int l, const G g) {
      return this->m_base.max_right(l, g);
    }
    template <class G>
    int min_left(const int r, const G g) {
      return this->m_base.min_left(r, g);
    }
  };
}

Back to top page