Slope Trick
(Src/Utility/SlopeTrick.hpp)

View this file on GitHub
Last update: 2024-05-02 00:23:12+09:00
Include: #include "Src/Utility/SlopeTrick.hpp"

概要

slope trick (1) 解説編で紹介されている操作をライブラリ化したもの。

取り扱う関数を $f$ 、傾きの変化する点の多重集合の要素数を $N$ とする。

当然だが、扱う $f$ は上記解説に書かれている制約を満たす必要がある。

ライブラリの使い方

テンプレート引数

template <class D, class C>

Dが $x$ の型、Cが $f(x)$ の型。

制約: std::is_integral<D>、std::is_integral<C>がstd::true_typeから派生する。

コンストラクタ

(1) SlopeTrick();
(2) SlopeTrick(const SlopeTrick&);
(3) SlopeTrick(SlopeTrick&&);

(1) $f(x) = 0$ で初期化する

(2) コピーコンストラクタ

(3) ムーブコンストラクタ

計算量

(1) 定数時間
(2) $O(N\log N)$
(3) 定数時間

operator=

(1) SlopeTrick& operator=(const SlopeTrick&)
(2) SlopeTrick& operator=(SlopeTrick&&)

計算量

(1) $O(N\log N)$
(2) 定数時間

min

C min() const

$\min f(x)$ を返す。

計算量

定数時間

argmin

std::pair<std::optional<D>, std::optional<D>> argmin() const

$\text{argmin} f(x)$ は区間になる。この左端、右端をこの順にstd::pairに入れて返す。

左端が $-\infty$ 、右端が $\infty$ の場合はstd::nulloptが返る。

計算量

定数時間

addConstant

void addConstant(C c)

$f(x) \leftarrow f(x) + c$ とする。

計算量

定数時間

addMax0XA

void addMax0XA(D a)

$f(x) \leftarrow f(x) + \max(0, x - a)$ とする。

計算量

$O(\log N)$

addMax0AX

void addMax0AX(D a)

$f(x) \leftarrow f(x) + \max(0, a - x)$ とする。

計算量

$O(\log N)$

addAbsoluteXA

void addAbsoluteXA(D a)

$f(x) \leftarrow f(x) +

x - a

$ とする。

計算量

$O(\log N)$

prefixMin

void prefixMin()

$f(x) \leftarrow \min_{x’\le x} f(x’)$ とする。

計算量

定数時間

suffixMin

void suffixMin()

$f(x) \leftarrow \min_{x’\ge x} f(x’)$ とする。

計算量

定数時間

slidingWindowMin

void slidingWindowMin(D a, D b)

$f(x) \leftarrow \min_{x - a\le x’\le x - b} f(x’)$ とする。符号注意。

計算量

定数時間

translation

void translation(D c)

$f(x) \leftarrow f(x - c)$ とする。

計算量

定数時間

enumerateL

std::vector<D> enumerateL() const

変化点の左側集合を返す。

計算量

$O(N\log N)$

enumerateR

std::vector<D> enumerateR() const

変化点の右側集合を返す。

計算量

$O(N\log N)$

f

C f(D x) const

$f(x)$ を返す。

計算量

$O(N\log N)$

clear

void clear()

$f(x)\leftarrow 0$ とする。

operator+=

SlopeTrick& operator+=(const SlopeTrick&)

左辺の関数に右辺の関数を足し込む。

計算量

$O(N\log^{2} N)$
マージテクをすると全体で $O(N\log^{2} N)$ を達成することも可能(例: じょうしょうツリー)

sizeL

inline SizeType sizeL() const

SizeType = zawa::usize (std::size_t)

左側集合のサイズを返す。

計算量

定数時間

sizeR

inline SizeType sizeR() const

右側集合のサイズを返す。

計算量

定数時間

size

inline SizeType size() const

$N$ を返す。

計算量

定数時間

メモ

Verified with

Code

#pragma once

#include <queue>
#include <optional>
#include <type_traits>
#include <vector>

namespace zawa {

    // domain, codomain
    template <class D, class C>
    class SlopeTrick {
        static_assert(std::is_integral_v<D>, "zawa::SlopeTrick::D must be integral");
        static_assert(std::is_integral_v<C>, "zawa::SlopeTrick::C must be integral");
    public:
        using SizeType = usize;
        SlopeTrick() = default;
        SlopeTrick(const SlopeTrick& st) : L_{st.L_}, R_{st.R_}, min_{st.min_} {}
        SlopeTrick(SlopeTrick&& st) : L_{std::move(st.L_)}, R_{std::move(st.R_)}, min_{st.min_} {}
        SlopeTrick& operator=(const SlopeTrick& st) {
            L_ = st.L_;
            R_ = st.R_;
            min_ = st.min_;
            return *this;
        }
        SlopeTrick& operator=(SlopeTrick&& st) {
            L_ = std::move(st.L_);
            R_ = std::move(st.R_);
            min_ = st.min_;
            return *this;
        }
        // get min
        C min() const {
            return min_;
        }
        // get [l0, r0]
        std::pair<std::optional<D>, std::optional<D>> argmin() const {
            return {
                L_.empty() ? std::nullopt : std::optional<D>{lvalue(L_.top())},
                R_.empty() ? std::nullopt : std::optional<D>{rvalue(R_.top())}
            };
        }
        // add y = c
        void addConstant(C c) {
            min_ += c;
        }
        // add y = max(0, x - a)
        void addMax0XA(D a) {
            if (L_.empty() or lvalue(L_.top()) <= a) {
                pushR(a);
            }
            else {
                pushR(lvalue(L_.top()));
                min_ += lvalue(L_.top()) - a;
                L_.pop();
                pushL(a);
            }
        }
        // add y = max(0, a - x)
        void addMax0AX(D a) {
            if (R_.empty() or a <= rvalue(R_.top())) {
                pushL(a);
            }
            else {
                pushL(rvalue(R_.top()));
                min_ += a - rvalue(R_.top());
                R_.pop();
                pushR(a);
            }
        }
        // add y = |x - a|
        void addAbsoluteXA(D a) {
            addMax0XA(a);
            addMax0AX(a);
        }
        // 前から累積minをとった関数に置き換える
        void prefixMin() {
            R_ = std::move(decltype(R_){});
            addR_ = D{0};
        }
        // 後ろから累積minをとった関数に置き換える
        void suffixMin() {
            L_ = std::move(decltype(L_){});
            addL_ = D{0};
        }
        // g(x) = min f(k) (x - a <= k <= x - b)に置き換える
        void slidingWindowMin(D a, D b) {
            addR_ += b;
            addL_ += a;
        }
        // x軸方向にc平行移動する
        void translation(D c) {
            slidingWindowMin(c, c);
        }
        // 傾きがk -> k + 1 (x < 0)となる点を列挙する
        std::vector<D> enumerateL() const {
            decltype(L_) L{L_};
            std::vector<D> res;
            while (L.size()) {
                res.emplace_back(lvalue(L.top()));
                L.pop();
            }
            return res;
        }
        // 傾きがk -> k + 1 (x >= 0)となる点を列挙する
        std::vector<D> enumerateR() const {
            decltype(R_) R{R_};
            std::vector<D> res;
            while (R.size()) {
                res.emplace_back(rvalue(R.top()));
                R.pop();
            }
            return res;
        }
        // get f(x)
        // 注意: O(N\log N)かかる
        C f(D x) const {
            C res{min_};
            for (auto l : enumerateL()) {
                res += std::max(D{0}, l - x);
            }
            for (auto r : enumerateR()) {
                res += std::max(D{0}, x - r);
            }
            return res;
        }
        void clear() {
            L_ = decltype(L_){};
            R_ = decltype(R_){};
            min_ = D{0};
        }
        SlopeTrick& operator+=(const SlopeTrick& st) {
            min_ += st.min();
            for (auto l : st.enumerateL()) {
                addMax0AX(l);
            }
            for (auto r : st.enumerateR()) {
                addMax0XA(r);
            }
            return *this;
        }
        inline SizeType sizeL() const {
            return L_.size();
        }
        inline SizeType sizeR() const {
            return R_.size();
        }
        inline SizeType size() const {
            return sizeL() + sizeR();
        }
    private:
        std::priority_queue<D> L_{};
        std::priority_queue<D, std::vector<D>, std::greater<D>> R_{};
        D addL_{}, addR_{};
        C min_{};

        inline D lvalue(D l) const noexcept {
            return l + addL_;
        }
        inline D rvalue(D r) const noexcept {
            return r + addR_;
        }
        inline void pushL(D v) noexcept {
            L_.push(v - addL_);
        }
        inline void pushR(D v) noexcept {
            R_.push(v - addR_);
        }
    };

} // namespace zawa

#line 2 "Src/Utility/SlopeTrick.hpp"

#include <queue>
#include <optional>
#include <type_traits>
#include <vector>

namespace zawa {

    // domain, codomain
    template <class D, class C>
    class SlopeTrick {
        static_assert(std::is_integral_v<D>, "zawa::SlopeTrick::D must be integral");
        static_assert(std::is_integral_v<C>, "zawa::SlopeTrick::C must be integral");
    public:
        using SizeType = usize;
        SlopeTrick() = default;
        SlopeTrick(const SlopeTrick& st) : L_{st.L_}, R_{st.R_}, min_{st.min_} {}
        SlopeTrick(SlopeTrick&& st) : L_{std::move(st.L_)}, R_{std::move(st.R_)}, min_{st.min_} {}
        SlopeTrick& operator=(const SlopeTrick& st) {
            L_ = st.L_;
            R_ = st.R_;
            min_ = st.min_;
            return *this;
        }
        SlopeTrick& operator=(SlopeTrick&& st) {
            L_ = std::move(st.L_);
            R_ = std::move(st.R_);
            min_ = st.min_;
            return *this;
        }
        // get min
        C min() const {
            return min_;
        }
        // get [l0, r0]
        std::pair<std::optional<D>, std::optional<D>> argmin() const {
            return {
                L_.empty() ? std::nullopt : std::optional<D>{lvalue(L_.top())},
                R_.empty() ? std::nullopt : std::optional<D>{rvalue(R_.top())}
            };
        }
        // add y = c
        void addConstant(C c) {
            min_ += c;
        }
        // add y = max(0, x - a)
        void addMax0XA(D a) {
            if (L_.empty() or lvalue(L_.top()) <= a) {
                pushR(a);
            }
            else {
                pushR(lvalue(L_.top()));
                min_ += lvalue(L_.top()) - a;
                L_.pop();
                pushL(a);
            }
        }
        // add y = max(0, a - x)
        void addMax0AX(D a) {
            if (R_.empty() or a <= rvalue(R_.top())) {
                pushL(a);
            }
            else {
                pushL(rvalue(R_.top()));
                min_ += a - rvalue(R_.top());
                R_.pop();
                pushR(a);
            }
        }
        // add y = |x - a|
        void addAbsoluteXA(D a) {
            addMax0XA(a);
            addMax0AX(a);
        }
        // 前から累積minをとった関数に置き換える
        void prefixMin() {
            R_ = std::move(decltype(R_){});
            addR_ = D{0};
        }
        // 後ろから累積minをとった関数に置き換える
        void suffixMin() {
            L_ = std::move(decltype(L_){});
            addL_ = D{0};
        }
        // g(x) = min f(k) (x - a <= k <= x - b)に置き換える
        void slidingWindowMin(D a, D b) {
            addR_ += b;
            addL_ += a;
        }
        // x軸方向にc平行移動する
        void translation(D c) {
            slidingWindowMin(c, c);
        }
        // 傾きがk -> k + 1 (x < 0)となる点を列挙する
        std::vector<D> enumerateL() const {
            decltype(L_) L{L_};
            std::vector<D> res;
            while (L.size()) {
                res.emplace_back(lvalue(L.top()));
                L.pop();
            }
            return res;
        }
        // 傾きがk -> k + 1 (x >= 0)となる点を列挙する
        std::vector<D> enumerateR() const {
            decltype(R_) R{R_};
            std::vector<D> res;
            while (R.size()) {
                res.emplace_back(rvalue(R.top()));
                R.pop();
            }
            return res;
        }
        // get f(x)
        // 注意: O(N\log N)かかる
        C f(D x) const {
            C res{min_};
            for (auto l : enumerateL()) {
                res += std::max(D{0}, l - x);
            }
            for (auto r : enumerateR()) {
                res += std::max(D{0}, x - r);
            }
            return res;
        }
        void clear() {
            L_ = decltype(L_){};
            R_ = decltype(R_){};
            min_ = D{0};
        }
        SlopeTrick& operator+=(const SlopeTrick& st) {
            min_ += st.min();
            for (auto l : st.enumerateL()) {
                addMax0AX(l);
            }
            for (auto r : st.enumerateR()) {
                addMax0XA(r);
            }
            return *this;
        }
        inline SizeType sizeL() const {
            return L_.size();
        }
        inline SizeType sizeR() const {
            return R_.size();
        }
        inline SizeType size() const {
            return sizeL() + sizeR();
        }
    private:
        std::priority_queue<D> L_{};
        std::priority_queue<D, std::vector<D>, std::greater<D>> R_{};
        D addL_{}, addR_{};
        C min_{};

        inline D lvalue(D l) const noexcept {
            return l + addL_;
        }
        inline D rvalue(D r) const noexcept {
            return r + addR_;
        }
        inline void pushL(D v) noexcept {
            L_.push(v - addL_);
        }
        inline void pushR(D v) noexcept {
            R_.push(v - addR_);
        }
    };

} // namespace zawa

Slope Trick (Src/Utility/SlopeTrick.hpp)

概要

ライブラリの使い方

テンプレート引数

コンストラクタ

operator=

min

argmin

addConstant

addMax0XA

addMax0AX

addAbsoluteXA

prefixMin

suffixMin

slidingWindowMin

translation

enumerateL

enumerateR

f

clear

operator+=

sizeL

sizeR

size

メモ

Verified with

Code

Slope Trick
(Src/Utility/SlopeTrick.hpp)