lib/segtree/segment_tree_raq.hpp

View this file on GitHub
Last update: 2026-03-15 03:14:58+09:00
Include: #include "lib/segtree/segment_tree_raq.hpp"

Depends on

Verified with

Code

#include <algorithm>
#include <utility>
#include "segtree/segment_tree.hpp"

template <class T>
struct segment_tree_range_add_range_max {
  private:
    struct Monoid {
        using P = std::pair<T, T>;
        using value_type = P;
        static constexpr P id() { return P(); }
        static constexpr P op(const P &lhs, const P &rhs) {
            return std::make_pair(std::max(lhs.first, lhs.second + rhs.first), lhs.second + rhs.second);
        }
    };

  public:
    segment_tree_range_add_range_max(int n) : st(n + 1, std::make_pair(T(), T())) {}
    segment_tree_range_add_range_max(int n, T e) : segment_tree_range_add_range_max(n) {
        st.set(0, std::make_pair(e, e));
    }

    T at(int k) { return this->st.prod(0, k + 1).second; }
    T get(int k) { return this->at(k); }

    void set(int k, T val) { this->apply(k, k + 1, val - at(k)); }
    void apply(int k, T val) { this->apply(k, k + 1, val); }
    void apply(int a, int b, T val) {
        auto x = this->st.get(a);
        this->st.set(a, std::make_pair(x.second + val, x.second + val));
        auto y = this->st.get(b);
        this->st.set(b, std::make_pair(y.second - val, y.second - val));
    }
    void add(int k, T val) { this->apply(k, k + 1, val); }
    void add(int a, int b, T val) { this->apply(a, b, val); }

    T prod(int a, int b) { return this->st.prod(0, a + 1).second + this->st.prod(a + 1, b).first; }

  private:
    segment_tree<Monoid> st;
};

template <class T>
struct segment_tree_range_add_range_min {
  private:
    struct Monoid {
        using P = std::pair<T, T>;
        using value_type = P;
        static constexpr P id() { return P(); }
        static constexpr P op(const P &lhs, const P &rhs) {
            return std::make_pair(std::min(lhs.first, lhs.second + rhs.first), lhs.second + rhs.second);
        }
    };

  public:
    segment_tree_range_add_range_min(int n) : st(n + 1, std::make_pair(T(), T())) {}
    segment_tree_range_add_range_min(int n, T e) : segment_tree_range_add_range_min(n) {
        st.set(0, std::make_pair(e, e));
    }

    T at(int k) { return this->st.prod(0, k + 1).second; }
    T get(int k) { return this->at(k); }

    void set(int k, T val) { this->apply(k, k + 1, val - at(k)); }
    void apply(int k, T val) { this->apply(k, k + 1, val); }
    void apply(int a, int b, T val) {
        auto x = this->st.get(a);
        this->st.set(a, std::make_pair(x.second + val, x.second + val));
        auto y = this->st.get(b);
        this->st.set(b, std::make_pair(y.second - val, y.second - val));
    }
    void add(int k, T val) { this->apply(k, k + 1, val); }
    void add(int a, int b, T val) { this->apply(a, b, val); }

    T prod(int a, int b) { return this->st.prod(0, a + 1).second + this->st.prod(a + 1, b).first; }

  private:
    segment_tree<Monoid> st;
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: segtree/segment_tree.hpp: line -1: no such header