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

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-24 02:34:04+09:00
• Include: #include "structure/others/slope-trick.hpp"
• Link: https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8

概要

区分線形凸関数 $f(x)$ を効率的に扱うためのデータ構造。

$f(x)$ の傾きが変化する点を優先度付きキューに持つことで, 特定の操作を簡潔に行うことが可能となる。傾きを $1$ ずつ変化させていく場合はこの実装で良いが, それ以外の場合は平衡二分探索木などの高度なデータ構造を用いる必要がある。

主にDPの高速化に用いられることが多い。

使い方

• query(): $f(x)$ の最小値とそれを満たす $x$ の最小値および最大値を返す。
• add_all(a): $f(x)$ に $a$ を加算する。
• add_a_minus_x(a): $f(x)$ に $\max(a - x, 0)$ を加算する。
• add_x_minus_a(a): $f(x)$ に $\max(x - a, 0)$ を加算する。
• add_abs(a): $f(x)$ に$abs(x-a)$ を加算する。
• clear_right(): $f(x) = \min_{y \le x} f(y)$ に置き換える。
• clear_left(): $f(x) = \min_{y \ge x} f(y)$ に置き換える。
• shift(a, b): $f(x) = \min_{x-b \le y \le x-a} f(y)$ に置き換える。$a \leq b$ を満たす必要がある。
• shift(a): $f(x) = f(x - a)$ に置き換える。
• get(x): $f(x)$ を返す。ただし $f$ を破壊する。
• merge(g): $f(x)$ に $g(x)$ を加算する. ただし $g$ を破壊する。

計算量

• query(), add_all(), clear_right(), clear_left(), shift(): $O(1)$
• get(): $O(Q)$
• merge(): $f, g$ の大きさをそれぞれ $N, M$ として $O(\min(N, M) \log \max(N, M))$
• それ以外の操作: $O(\log Q)$

Code

/**
 * @brief Slope-Trick
 * 
 * @see https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8
 */
template< typename T >
struct SlopeTrick {
 
  const T INF = numeric_limits< T >::max() / 3;
 
  T min_f;
  priority_queue< T, vector< T >, less<> > L;
  priority_queue< T, vector< T >, greater<> > R;
  T add_l, add_r;
 
private:
  void push_R(const T &a) {
    R.push(a - add_r);
  }
 
  T top_R() const {
    if(R.empty()) return INF;
    else return R.top() + add_r;
  }
 
  T pop_R() {
    T val = top_R();
    if(not R.empty()) R.pop();
    return val;
  }
 
  void push_L(const T &a) {
    L.push(a - add_l);
  }
 
  T top_L() const {
    if(L.empty()) return -INF;
    else return L.top() + add_l;
  }
 
  T pop_L() {
    T val = top_L();
    if(not L.empty()) L.pop();
    return val;
  }
 
  size_t size() {
    return L.size() + R.size();
  }
 
public:
  SlopeTrick() : min_f(0), add_l(0), add_r(0) {}
 
  struct Query {
    T lx, rx, min_f;
  };
 
  // return min f(x)
  Query query() const {
    return (Query) {top_L(), top_R(), min_f};
  }
 
  // f(x) += a
  void add_all(const T &a) {
    min_f += a;
  }
 
  // add \_
  // f(x) += max(a - x, 0)
  void add_a_minus_x(const T &a) {
    min_f += max(T(0), a - top_R());
    push_R(a);
    push_L(pop_R());
  }
 
  // add _/
  // f(x) += max(x - a, 0)
  void add_x_minus_a(const T &a) {
    min_f += max(T(0), top_L() - a);
    push_L(a);
    push_R(pop_L());
  }
 
  // add \/
  // f(x) += abs(x - a)
  void add_abs(const T &a) {
    add_a_minus_x(a);
    add_x_minus_a(a);
  }
 
  // \/ -> \_
  // f_{new} (x) = min f(y) (y <= x)
  void clear_right() {
    while(not R.empty()) R.pop();
  }
 
  // \/ -> _/
  // f_{new} (x) = min f(y) (y >= x)
  void clear_left() {
    while(not L.empty()) L.pop();
  }
 
  // \/ -> \_/
  // f_{new} (x) = min f(y) (x-b <= y <= x-a)
  void shift(const T &a, const T &b) {
    assert(a <= b);
    add_l += a;
    add_r += b;
  }
 
  // \/. -> .\/
  // f_{new} (x) = f(x - a)
  void shift(const T &a) {
    shift(a, a);
  }
 
  // L, R を破壊する
  T get(const T &x) {
    T ret = min_f;
    while(not L.empty()) {
      ret += max(T(0), pop_L() - x);
    }
    while(not R.empty()) {
      ret += max(T(0), x - pop_R());
    }
    return ret;
  }
 
  void merge(SlopeTrick &st) {
    if(st.size() > size()) {
      swap(st.L, L);
      swap(st.R, R);
      swap(st.add_l, add_l);
      swap(st.add_r, add_r);
      swap(st.min_f, min_f);
    }
    while(not st.R.empty()) {
      add_x_minus_a(st.pop_R());
    }
    while(not st.L.empty()) {
      add_a_minus_x(st.pop_L());
    }
    min_f += st.min_f;
  }
};

#line 1 "structure/others/slope-trick.hpp"
/**
 * @brief Slope-Trick
 * 
 * @see https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8
 */
template< typename T >
struct SlopeTrick {
 
  const T INF = numeric_limits< T >::max() / 3;
 
  T min_f;
  priority_queue< T, vector< T >, less<> > L;
  priority_queue< T, vector< T >, greater<> > R;
  T add_l, add_r;
 
private:
  void push_R(const T &a) {
    R.push(a - add_r);
  }
 
  T top_R() const {
    if(R.empty()) return INF;
    else return R.top() + add_r;
  }
 
  T pop_R() {
    T val = top_R();
    if(not R.empty()) R.pop();
    return val;
  }
 
  void push_L(const T &a) {
    L.push(a - add_l);
  }
 
  T top_L() const {
    if(L.empty()) return -INF;
    else return L.top() + add_l;
  }
 
  T pop_L() {
    T val = top_L();
    if(not L.empty()) L.pop();
    return val;
  }
 
  size_t size() {
    return L.size() + R.size();
  }
 
public:
  SlopeTrick() : min_f(0), add_l(0), add_r(0) {}
 
  struct Query {
    T lx, rx, min_f;
  };
 
  // return min f(x)
  Query query() const {
    return (Query) {top_L(), top_R(), min_f};
  }
 
  // f(x) += a
  void add_all(const T &a) {
    min_f += a;
  }
 
  // add \_
  // f(x) += max(a - x, 0)
  void add_a_minus_x(const T &a) {
    min_f += max(T(0), a - top_R());
    push_R(a);
    push_L(pop_R());
  }
 
  // add _/
  // f(x) += max(x - a, 0)
  void add_x_minus_a(const T &a) {
    min_f += max(T(0), top_L() - a);
    push_L(a);
    push_R(pop_L());
  }
 
  // add \/
  // f(x) += abs(x - a)
  void add_abs(const T &a) {
    add_a_minus_x(a);
    add_x_minus_a(a);
  }
 
  // \/ -> \_
  // f_{new} (x) = min f(y) (y <= x)
  void clear_right() {
    while(not R.empty()) R.pop();
  }
 
  // \/ -> _/
  // f_{new} (x) = min f(y) (y >= x)
  void clear_left() {
    while(not L.empty()) L.pop();
  }
 
  // \/ -> \_/
  // f_{new} (x) = min f(y) (x-b <= y <= x-a)
  void shift(const T &a, const T &b) {
    assert(a <= b);
    add_l += a;
    add_r += b;
  }
 
  // \/. -> .\/
  // f_{new} (x) = f(x - a)
  void shift(const T &a) {
    shift(a, a);
  }
 
  // L, R を破壊する
  T get(const T &x) {
    T ret = min_f;
    while(not L.empty()) {
      ret += max(T(0), pop_L() - x);
    }
    while(not R.empty()) {
      ret += max(T(0), x - pop_R());
    }
    return ret;
  }
 
  void merge(SlopeTrick &st) {
    if(st.size() > size()) {
      swap(st.L, L);
      swap(st.R, R);
      swap(st.add_l, add_l);
      swap(st.add_r, add_r);
      swap(st.min_f, min_f);
    }
    while(not st.R.empty()) {
      add_x_minus_a(st.pop_R());
    }
    while(not st.L.empty()) {
      add_a_minus_x(st.pop_L());
    }
    min_f += st.min_f;
  }
};

Back to top page