Slope Trick
(data_structure/slope_trick.hpp)

• View this file on GitHub
• Last update: 2024-03-12 18:09:18+09:00
• Include: #include "data_structure/slope_trick.hpp"
• Link: https://maspypy.com/slope-trick-1-%e8%a7%a3%e8%aa%ac%e7%b7%a8

説明

区分線形凸関数 $f$ を管理するデータ構造。

min()

最小値を返す。 $O(1)$

argmin()

最小値となる $x$ 座標の範囲 $[l, r]$ を返す。 $O(1)$

add_all(T a)

全ての $x$ に対して $a$ を加算する。 $O(1)$

add_x_minus_a(T a)

$(x-a)_+ = \max(0, x - a)$ を加算する。 $O(\log N)$

add_a_minus_x(T a)

$(a-x)_+ = \max(0, a-x)$ を加算する。 $O(\log N)$

add_abs(T a)

$\lvert x - a \rvert$ を加算する。 $O(\log N)$

sliding_window_minimum(T a, T b)

$a \leq b$ として、

\[g(x) = \min_{y \in [x-b, x-a]} f(y)\]

で定まる $g$ を計算し $f$ とする。 $O(1)$

shift(T a)

$g = f(x-a)$ となる $g$ を計算し $f$ とする。 $O(1)$

merge(Self st)

Slope Trickをマージする。Weighted union ruleで、サイズの大きいほうにマージする。

right_cumulative_min()

右側累積和を取る。つまり、

\[g(x) = \min_{y \geq x} f(y)\]

となる $g$ を計算し、 $f = g$ とする。 $O(1)$

left_cumulative_min()

累積和を取る。つまり、

\[g(x) = \min_{y \leq x} f(y)\]

となる $g$ を計算し、 $f = g$ とする。 $O(1)$

Verified with

• test/yuki/yuki_1077.test.cpp

Code

#pragma once

#include <cassert>
#include <limits>
#include <queue>
#include <vector>

/*
    reference: https://maspypy.com/slope-trick-1-%e8%a7%a3%e8%aa%ac%e7%b7%a8
*/

namespace ebi {

template <class T> struct slope_trick {
  private:
    using Self = slope_trick<T>;

    void pop_L() {
        if (L.empty()) return;
        L.pop();
        return;
    }

    T top_L() const {
        if (L.empty()) return -INF;
        return L.top() + add_L;
    }

    void push_L(const T &a) {
        L.push(a - add_L);
        return;
    }

    void pop_R() {
        if (R.empty()) return;
        R.pop();
        return;
    }

    T top_R() const {
        if (R.empty()) return INF;
        return R.top() + add_R;
    }

    void push_R(const T &a) {
        R.push(a - add_R);
        return;
    }

    int size() {
        return L.size() + R.size();
    }

    void swap(Self &a, Self &b) {
        std::swap(a.min_f, b.min_f);
        std::swap(a.L, b.L);
        std::swap(a.R, b.R);
        std::swap(a.add_L, b.add_L);
        std::swap(a.add_R, b.add_R);
        return;
    }

  public:
    slope_trick() : min_f(0), add_L(0), add_R(0) {}

    T min() const {
        return min_f;
    }

    std::pair<T, T> argmin() const {
        return {top_L(), top_R()};
    }

    void add_all(const T &a) {
        min_f += a;
        return;
    }

    // add (x-a)_+
    void add_x_minus_a(const T &a) {
        min_f += std::max(T(0), top_L() - a);
        if (top_L() <= a) {
            push_R(a);
        } else {
            push_L(a);
            push_R(top_L());
            pop_L();
        }
        return;
    }

    // add (a-x)_+
    void add_a_minus_x(const T &a) {
        min_f += std::max(T(0), a - top_R());
        if (top_R() >= a) {
            push_L(a);
        } else {
            push_R(a);
            push_L(top_R());
            pop_R();
        }
        return;
    }

    // add |x-a|
    void add_abs(const T &a) {
        add_x_minus_a(a);
        add_a_minus_x(a);
        return;
    }

    void sliding_window_minimum(const T &a, const T &b) {
        assert(a <= b);
        add_L += a;
        add_R += b;
        return;
    }

    void shift(const T &a) {
        sliding_window_minimum(a, a);
    }

    void merge(Self &st) {
        if (st.size() > size()) {
            swap((*this), st);
        }
        min_f += st.min_f;
        while (!st.L.empty()) {
            add_a_minus_x(st.top_L());
            st.pop_L();
        }
        while (!st.R.empty()) {
            add_x_minus_a(st.top_R());
            st.pop_R();
        }
        return;
    }

    // __/
    void right_cumulative_min() {
        L = std::priority_queue<T>();
    }

    // \__
    void left_cumulative_min() {
        R = std::priority_queue<T, std::vector<T>, std::greater<T>>();
    }

  private:
    T min_f;
    std::priority_queue<T> L;
    std::priority_queue<T, std::vector<T>, std::greater<T>> R;
    T add_L, add_R;
    const T INF = std::numeric_limits<T>::max() / 4;
};

}  // namespace ebi

#line 2 "data_structure/slope_trick.hpp"

#include <cassert>
#include <limits>
#include <queue>
#include <vector>

/*
    reference: https://maspypy.com/slope-trick-1-%e8%a7%a3%e8%aa%ac%e7%b7%a8
*/

namespace ebi {

template <class T> struct slope_trick {
  private:
    using Self = slope_trick<T>;

    void pop_L() {
        if (L.empty()) return;
        L.pop();
        return;
    }

    T top_L() const {
        if (L.empty()) return -INF;
        return L.top() + add_L;
    }

    void push_L(const T &a) {
        L.push(a - add_L);
        return;
    }

    void pop_R() {
        if (R.empty()) return;
        R.pop();
        return;
    }

    T top_R() const {
        if (R.empty()) return INF;
        return R.top() + add_R;
    }

    void push_R(const T &a) {
        R.push(a - add_R);
        return;
    }

    int size() {
        return L.size() + R.size();
    }

    void swap(Self &a, Self &b) {
        std::swap(a.min_f, b.min_f);
        std::swap(a.L, b.L);
        std::swap(a.R, b.R);
        std::swap(a.add_L, b.add_L);
        std::swap(a.add_R, b.add_R);
        return;
    }

  public:
    slope_trick() : min_f(0), add_L(0), add_R(0) {}

    T min() const {
        return min_f;
    }

    std::pair<T, T> argmin() const {
        return {top_L(), top_R()};
    }

    void add_all(const T &a) {
        min_f += a;
        return;
    }

    // add (x-a)_+
    void add_x_minus_a(const T &a) {
        min_f += std::max(T(0), top_L() - a);
        if (top_L() <= a) {
            push_R(a);
        } else {
            push_L(a);
            push_R(top_L());
            pop_L();
        }
        return;
    }

    // add (a-x)_+
    void add_a_minus_x(const T &a) {
        min_f += std::max(T(0), a - top_R());
        if (top_R() >= a) {
            push_L(a);
        } else {
            push_R(a);
            push_L(top_R());
            pop_R();
        }
        return;
    }

    // add |x-a|
    void add_abs(const T &a) {
        add_x_minus_a(a);
        add_a_minus_x(a);
        return;
    }

    void sliding_window_minimum(const T &a, const T &b) {
        assert(a <= b);
        add_L += a;
        add_R += b;
        return;
    }

    void shift(const T &a) {
        sliding_window_minimum(a, a);
    }

    void merge(Self &st) {
        if (st.size() > size()) {
            swap((*this), st);
        }
        min_f += st.min_f;
        while (!st.L.empty()) {
            add_a_minus_x(st.top_L());
            st.pop_L();
        }
        while (!st.R.empty()) {
            add_x_minus_a(st.top_R());
            st.pop_R();
        }
        return;
    }

    // __/
    void right_cumulative_min() {
        L = std::priority_queue<T>();
    }

    // \__
    void left_cumulative_min() {
        R = std::priority_queue<T, std::vector<T>, std::greater<T>>();
    }

  private:
    T min_f;
    std::priority_queue<T> L;
    std::priority_queue<T, std::vector<T>, std::greater<T>> R;
    T add_L, add_R;
    const T INF = std::numeric_limits<T>::max() / 4;
};

}  // namespace ebi

Back to top page