Segment Tree Beats (based on atcoder::lazy_segtree)
(segmenttree/acl_beats.hpp)

• View this file on GitHub
• Last update: 2025-10-26 13:49:19+09:00
• Include: #include "segmenttree/acl_beats.hpp"

ACL-based segment tree beats

Link

• ACL reference
• My blog

Depends on

• Lazy Segtree (based on atcoder::lazy_segtree) (segmenttree/acl_lazysegtree.hpp)

Required by

• segmenttree/trees/acl_range-bitwiseandor-range-max.hpp
• segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp
• segmenttree/trees/range-chmax-add-range-sum.hpp
• segmenttree/trees/range-chmax-range-sum.hpp
• segmenttree/trees/range-chmin-chmax-add-range-sum.hpp

Verified with

• segmenttree/test/beats.test.cpp
• segmenttree/test/beats_gcd.test.cpp
• segmenttree/test/beats_random_test.test.cpp
• segmenttree/test/beats_range-chmax-add-range-sum.aoj0427.test.cpp
• segmenttree/test/range-chmax-range-sum.yuki3314.test.cpp

Code

#pragma once
#include "acl_lazysegtree.hpp"

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);
        }
    }
};

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.7/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.7/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.7/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.7/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 355, in update
    raise BundleErrorAt(path, i + 1, "found codes out of include guard")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: segmenttree/acl_lazysegtree.hpp: line 56: found codes out of include guard

Back to top page