Slope Trick
(data-structure/slope_trick.hpp)

• View this file on GitHub
• Last update: 2024-01-08 02:22:28+09:00
• Include: #include "data-structure/slope_trick.hpp"

Description

Slope Trick は，区分線形凸関数 $f: T \mapsto T$ を管理するテクニックである．傾きの変化点を，傾きが正である部分と負である部分で別々に優先度付きキューで管理することで，この関数に対する様々な操作を高速に処理する．

空間計算量: $O(n)$

Operations

• void add_const(T a)
  • $a$ を加える
  • 時間計算量: $O(1)$
• void add_x_minus_a(T a)
  • $\max(0, x - a)$ を加える
  • 時間計算量: $O(\log n)$
• void add_a_minus_x(T a)
  • $\max(0, a - x)$ を加える
  • 時間計算量: $O(\log n)$
• void add_abs(T a)
  • $\vert x - a\vert$ を加える
  • 時間計算量: $O(\log n)$
• void clear_left()
  • $g(x) := \min_{y \leq x} f(y)$ として，$f$ を $g$ に置き換える
  • 時間計算量: $O(n)$
• void clear_right()
  • $g(x) := \min_{y \geq x} f(y)$ として，$f$ を $g$ に置き換える
  • 時間計算量: $O(n)$
• void shift(T a)
  • $g(x) := f(x - a)$ として，$f$ を $g$ に置き換える
  • 時間計算量: $O(1)$
• void shift(T a, T b)
  • $g(x) := \min_{x - b \leq y \leq x - a} f(y)$ として，$f$ を $g$ に置き換える
  • 時間計算量: $O(1)$
• T get_min()
  • $f$ の最小値を返す
  • 時間計算量: $O(1)$
• T get(T x)
  • $f(x)$ を返す
  • 時間計算量: $O(n)$

Note

slope trick では，

• $a$ だけ平行移動: $O(1)$
• 傾き $c$ の関数を加算: $O(\vert c \vert \log n)$

となる．凸共役を取ることで，

• $a$ だけ平行移動: $O(\vert a \vert \log n)$
• 傾き $c$ の関数を加算: $O(1)$

にできる．(参考文献参照)

Reference

• slope trick (1) 解説編
• slope trick (3) slope trick の凸共役
• verify: https://atcoder.jp/contests/abc217/submissions/25616122

Code

#pragma once
#include <functional>
#include <limits>
#include <queue>
#include <vector>

template <typename T>
class SlopeTrick {
   public:
    SlopeTrick() {
        const T INF = std::numeric_limits<T>::max() / 2;
        left.push(-INF);
        right.push(INF);
    }

    void add_const(T a) { min_y += a; }

    void add_x_minus_a(T a) {
        T l = top_l();
        if (l < a) {
            push_r(a);
        } else {
            min_y += l - a;
            push_l(a);
            push_r(pop_l());
        }
    }

    void add_a_minus_x(T a) {
        T r = top_r();
        if (a < r) {
            push_l(a);
        } else {
            min_y += a - r;
            push_r(a);
            push_l(pop_r());
        }
    }

    void add_abs(T a) {
        add_x_minus_a(a);
        add_a_minus_x(a);
    }

    void clear_left() { left.clear(); }
    void clear_right() { right.clear(); }

    void shift(T a) { shift(a, a); }

    void shift(T a, T b) {
        add_l += a;
        add_r += b;
    }

    T get_min() { return min_y; }

    T get(T x) {
        T ret = min_y;
        std::priority_queue<T, std::vector<T>> tmp_l;
        std::priority_queue<T, std::vector<T>, std::greater<T>> tmp_r;
        while (!left.empty()) {
            T a = pop_l();
            ret += max(T(0), a - x);
            tmp_l.push(a);
        }
        while (!right.empty()) {
            T a = pop_r();
            ret += max(T(0), x - a);
            tmp_r.push(a);
        }
        left.swap(tmp_l);
        right.swap(tmp_r);
        add_l = add_r = 0;
        return ret;
    }

   private:
    T min_y = 0, add_l = 0, add_r = 0;
    std::priority_queue<T, std::vector<T>> left;
    std::priority_queue<T, std::vector<T>, std::greater<T>> right;

    void push_l(T a) { left.push(a - add_l); }
    void push_r(T a) { right.push(a - add_r); }

    T top_l() { return left.top() + add_l; }
    T top_r() { return right.top() + add_r; }

    T pop_l() {
        T a = top_l();
        left.pop();
        return a;
    }

    T pop_r() {
        T a = top_r();
        right.pop();
        return a;
    }
};

#line 2 "data-structure/slope_trick.hpp"
#include <functional>
#include <limits>
#include <queue>
#include <vector>

template <typename T>
class SlopeTrick {
   public:
    SlopeTrick() {
        const T INF = std::numeric_limits<T>::max() / 2;
        left.push(-INF);
        right.push(INF);
    }

    void add_const(T a) { min_y += a; }

    void add_x_minus_a(T a) {
        T l = top_l();
        if (l < a) {
            push_r(a);
        } else {
            min_y += l - a;
            push_l(a);
            push_r(pop_l());
        }
    }

    void add_a_minus_x(T a) {
        T r = top_r();
        if (a < r) {
            push_l(a);
        } else {
            min_y += a - r;
            push_r(a);
            push_l(pop_r());
        }
    }

    void add_abs(T a) {
        add_x_minus_a(a);
        add_a_minus_x(a);
    }

    void clear_left() { left.clear(); }
    void clear_right() { right.clear(); }

    void shift(T a) { shift(a, a); }

    void shift(T a, T b) {
        add_l += a;
        add_r += b;
    }

    T get_min() { return min_y; }

    T get(T x) {
        T ret = min_y;
        std::priority_queue<T, std::vector<T>> tmp_l;
        std::priority_queue<T, std::vector<T>, std::greater<T>> tmp_r;
        while (!left.empty()) {
            T a = pop_l();
            ret += max(T(0), a - x);
            tmp_l.push(a);
        }
        while (!right.empty()) {
            T a = pop_r();
            ret += max(T(0), x - a);
            tmp_r.push(a);
        }
        left.swap(tmp_l);
        right.swap(tmp_r);
        add_l = add_r = 0;
        return ret;
    }

   private:
    T min_y = 0, add_l = 0, add_r = 0;
    std::priority_queue<T, std::vector<T>> left;
    std::priority_queue<T, std::vector<T>, std::greater<T>> right;

    void push_l(T a) { left.push(a - add_l); }
    void push_r(T a) { right.push(a - add_r); }

    T top_l() { return left.top() + add_l; }
    T top_r() { return right.top() + add_r; }

    T pop_l() {
        T a = top_l();
        left.pop();
        return a;
    }

    T pop_r() {
        T a = top_r();
        right.pop();
        return a;
    }
};

Back to top page