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

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-27 01:27:28+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