Slope Trick
(data-structure/slope-trick.hpp)

• View this file on GitHub
• Last update: 2023-11-04 18:25:32+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(x)$ を管理するデータ構造。

詳しい内容は Link を参照。

• get_min() : $f(x)$ の最小値を返す。$O(1)$
• get_min_lr() : $f(x)$ の最小値及び、最小値を取る値域 $[l_0, r_0]$ を返す。$O(1)$
• add_const(T a) : 定数関数 $f(x) = a$ を追加する。$O(1)$
• add_right(T a) : $f(x)$ に関数 $\max(x - a, 0)$ を追加する。$O(\log N)$
• add_left(T a) : $f(x)$ に関数 $\max(a - x, 0)$ を追加する。$O(\log N)$
• add_abs(T a) : $f(x)$ に関数 $\mathrm{abs}(x-a)$ を追加する。$O(\log N)$
• clear_right() : $f(x)$ を $g(x) = \min_{y \leq x} f(y)$ に変更する。$O(1)$
• clear_left() : $f(x)$ を $g(x) = \min_{y \geq x} f(y)$ に変更する。$O(1)$
• shift(T a, T b) : $f(x)$ を $g(x) = \min_{x - b \leq y \leq x - a} f(y)$ に変更する。ただし $a \leq b$ が条件。$O(1)$
• shift(T a) : $f(x)$ を $g(x) = f(x - a)$ に変更する。$O(1)$
• merge(SlopeTrick& g) : $f$ に $g$ を加える。$g$ は空になる。
• eval(T x) : $f(x)$ を計算する。計算後、中身は空になる。

Code

#pragma once

#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <vector>
#include <utility>

// ref: https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8
template <typename T> struct SlopeTrick {
    const T inf = std::numeric_limits<T>::max() / 3;

    T min_f, add_L, add_R;
    std::priority_queue<T> L;
    std::priority_queue<T, std::vector<T>, std::greater<T>> R;

  private:
    void push_L(T a) { L.push(a - add_L); }
    T top_L() {
        if(L.empty()) return -inf;
        return L.top() + add_L;
    }
    T pop_L() {
        T ret = top_L();
        if(!L.empty()) L.pop();
        return ret;
    }
    void push_R(T a) { R.push(a - add_R); }
    T top_R() {
        if(R.empty()) return inf;
        return R.top() + add_R;
    }
    T pop_R() {
        T ret = top_R();
        if(!R.empty()) R.pop();
        return ret;
    }

  public:
    SlopeTrick() : min_f(0), add_L(0), add_R(0) {}
    T get_min() const { return min_f; }
    std::tuple<T, T, T> get_min_lr() const { return {min_f, top_L(), top_R()}; }
    // 定数関数 f(x) = a を追加
    void add_const(T a) { min_f += a; }
    // f(x) = (x - a)+ を追加
    void add_right(T a) {
        min_f += std::max(top_L() - a, T(0));
        push_L(a);
        T t = pop_L();
        push_R(t);
    }
    // f(x) = (a - x)+ を追加
    void add_left(T a) {
        min_f += std::max(a - top_R(), T(0));
        push_R(a);
        T t = pop_R();
        push_L(t);
    }
    // f(x) = |x - a| = (x - a)+ + (a - x)+ を追加
    void add_abs(T a) {
        add_left(a);
        add_right(a);
    }
    // (左側)累積min
    // g(x) := min_{y <= x} f(y) なる g に変更
    void clear_right() {
        while(!R.empty()) R.pop();
    }
    // (右側)累積min
    // g(x) := min_{y >= x} f(y) なる g に変更
    void clear_left() {
        while(!L.empty()) L.pop();
    }
    // スライド最小値関数
    // g(x) := min_{x - b <= y <= x - a} f(y) (a <= b) なる g に変更
    void shift(T a, T b) {
        assert(a <= b);
        add_L += a;
        add_R += b;
    }
    // 平行移動
    // g(x) := f(x - a) なる g に変更
    void shift(T a) { shift(a, a); }
    size_t size() const { return L.size() + R.size(); }
    void swap(SlopeTrick& rhs) {
        std::swap(min_f, rhs.min_f);
        std::swap(add_L, rhs.add_L);
        std::swap(add_R, rhs.add_R);
        std::swap(L, rhs.L);
        std::swap(R, rhs.R);
    }
    void merge(SlopeTrick& rhs) {
        if(size() < rhs.size()) swap(rhs);
        while(!rhs.L.empty()) add_left(rhs.pop_L());
        while(!rhs.R.empty()) add_right(rhs.pop_R());
        min_f += rhs.min_f;
    }
    // L, R は空になる
    T eval(T x) {
        T ret = min_f;
        while(!L.empty()) ret += max(T(0), pop_L() - x);
        while(!R.empty()) ret += max(T(0), x - pop_R());
        return ret;
    }
};

#line 2 "data-structure/slope-trick.hpp"

#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <vector>
#include <utility>

// ref: https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8
template <typename T> struct SlopeTrick {
    const T inf = std::numeric_limits<T>::max() / 3;

    T min_f, add_L, add_R;
    std::priority_queue<T> L;
    std::priority_queue<T, std::vector<T>, std::greater<T>> R;

  private:
    void push_L(T a) { L.push(a - add_L); }
    T top_L() {
        if(L.empty()) return -inf;
        return L.top() + add_L;
    }
    T pop_L() {
        T ret = top_L();
        if(!L.empty()) L.pop();
        return ret;
    }
    void push_R(T a) { R.push(a - add_R); }
    T top_R() {
        if(R.empty()) return inf;
        return R.top() + add_R;
    }
    T pop_R() {
        T ret = top_R();
        if(!R.empty()) R.pop();
        return ret;
    }

  public:
    SlopeTrick() : min_f(0), add_L(0), add_R(0) {}
    T get_min() const { return min_f; }
    std::tuple<T, T, T> get_min_lr() const { return {min_f, top_L(), top_R()}; }
    // 定数関数 f(x) = a を追加
    void add_const(T a) { min_f += a; }
    // f(x) = (x - a)+ を追加
    void add_right(T a) {
        min_f += std::max(top_L() - a, T(0));
        push_L(a);
        T t = pop_L();
        push_R(t);
    }
    // f(x) = (a - x)+ を追加
    void add_left(T a) {
        min_f += std::max(a - top_R(), T(0));
        push_R(a);
        T t = pop_R();
        push_L(t);
    }
    // f(x) = |x - a| = (x - a)+ + (a - x)+ を追加
    void add_abs(T a) {
        add_left(a);
        add_right(a);
    }
    // (左側)累積min
    // g(x) := min_{y <= x} f(y) なる g に変更
    void clear_right() {
        while(!R.empty()) R.pop();
    }
    // (右側)累積min
    // g(x) := min_{y >= x} f(y) なる g に変更
    void clear_left() {
        while(!L.empty()) L.pop();
    }
    // スライド最小値関数
    // g(x) := min_{x - b <= y <= x - a} f(y) (a <= b) なる g に変更
    void shift(T a, T b) {
        assert(a <= b);
        add_L += a;
        add_R += b;
    }
    // 平行移動
    // g(x) := f(x - a) なる g に変更
    void shift(T a) { shift(a, a); }
    size_t size() const { return L.size() + R.size(); }
    void swap(SlopeTrick& rhs) {
        std::swap(min_f, rhs.min_f);
        std::swap(add_L, rhs.add_L);
        std::swap(add_R, rhs.add_R);
        std::swap(L, rhs.L);
        std::swap(R, rhs.R);
    }
    void merge(SlopeTrick& rhs) {
        if(size() < rhs.size()) swap(rhs);
        while(!rhs.L.empty()) add_left(rhs.pop_L());
        while(!rhs.R.empty()) add_right(rhs.pop_R());
        min_f += rhs.min_f;
    }
    // L, R は空になる
    T eval(T x) {
        T ret = min_f;
        while(!L.empty()) ret += max(T(0), pop_L() - x);
        while(!R.empty()) ret += max(T(0), x - pop_R());
        return ret;
    }
};

Back to top page