slope trick
(include/emthrm/data_structure/slope_trick.hpp)

• View this file on GitHub
• Last update: 2022-12-15 22:18:37+09:00
• Include: #include "emthrm/data_structure/slope_trick.hpp"

各区分の傾きが整数な凸区分線形関数 (convex piecewise linear function) を管理するテクニック

時間計算量

区分の数を $N$ とおく。

	時間計算量
最小値の取得	$O(1)$
$\mathrm{argmin}_x f(x)$	$O(1)$
$f(x)$	$O(N)$
定数の加算	$O(1)$
$(x - a)^+$ の加算	$O(\log{N})$
$(a - x)^+$ の加算	$O(\log{N})$
$\lvert x - a \rvert$ の加算	$O(\log{N})$
累積 $\min$	amortized $O(1)$
逆側累積 $\min$	amortized $O(1)$
平行移動	$O(1)$
スライド最小値	$O(1)$

仕様

template <typename T>
struct SegmentTree;

メンバ変数

名前	説明
const T inf	$\infty$

メンバ関数

名前	効果・戻り値	要件
explicit SlopeTrick(const T min_f = 0, const T inf = std::numeric_limits<T>::max());	$f(x) = \mathrm{minF}$ を管理する。
T min() const;	$\min_x f(x)$
std::pair<T, T> argmin() const;	$\mathrm{argmin}_x f(x)$
template <typename U> U f(const U x);	$f(x)$
void constant_function(const T c);	$f(x) \gets f(x) + c$
void x_minus_a(const T a);	$f(x) \gets f(x) + (x - a)^+$
void a_minus_x(const T a);	$f(x) \gets f(x) + (a - x)^+$
void abs_x_minus_a(const T a);	$f(x) \gets f(x) + \lvert x - a \rvert$
void cumulative_min();	$f(x) \gets \min \lbrace f(y) \mid y \leq x \rbrace$
void rcumulative_min();	$f(x) \gets \min \lbrace f(y) \mid y \geq x \rbrace$
void translate(const T a);	$f(x) \gets f(x - a)$
void sliding_window_minimum(const T a, const T b);	$f(x) \gets \min \lbrace f(y) \mid y \in \lbrack x - b, x - a \rbrack \rbrace$	$a \leq b$

参考文献

• https://codeforces.com/blog/entry/47821
• https://maspypy.com/slope-trick-1-%e8%a7%a3%e8%aa%ac%e7%b7%a8
• https://github.com/ei1333/library/blob/6c2f9fa7ff07da182f3832f827c0c84d52e2e8d8/structure/others/slope-trick.cpp

TODO

• 一般化
  • https://github.com/ei1333/library/blob/af69da96544930d59e797c12ca977918df5e2a58/structure/others/generalized-slope-trick.cpp

Submissons

https://atcoder.jp/contests/arc123/submissions/24994392

Verified with

• データ構造/slope trick (test/data_structure/slope_trick.test.cpp)

Code

#ifndef EMTHRM_DATA_STRUCTURE_SLOPE_TRICK_HPP_
#define EMTHRM_DATA_STRUCTURE_SLOPE_TRICK_HPP_

#include <cassert>
#include <functional>
#include <limits>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>

namespace emthrm {

template <typename T>
struct SlopeTrick {
  const T inf;

  explicit SlopeTrick(
      const T min_f = 0, const T inf = std::numeric_limits<T>::max())
      : inf(inf), added_l(0), added_r(0), min_f(min_f) {}

  T min() const { return min_f; }
  std::pair<T, T> argmin() const { return {top_l(), top_r()}; }

  template <typename U>
  U f(const U x) {
    U f_x = min_f;
    std::vector<T> tmp;
    for (; top_l() > x; l.pop()) {
      const T t = top_l();
      f_x += t - x;
      tmp.emplace_back(t);
    }
    for (; !tmp.empty(); tmp.pop_back()) {
      emplace_l(tmp.back());
    }
    for (; top_r() < x; r.pop()) {
      const T t = top_r();
      f_x += x - t;
      tmp.emplace_back(t);
    }
    for (; !tmp.empty(); tmp.pop_back()) {
      emplace_r(tmp.back());
    }
    return f_x;
  }

  void constant_function(const T c) { min_f += c; }

  void x_minus_a(const T a) {
    const T t = top_l();
    if (t <= a) {
      emplace_r(a);
    } else {
      min_f += t - a;
      emplace_l(a);
      l.pop();
      emplace_r(t);
    }
  }

  void a_minus_x(const T a) {
    const T t = top_r();
    if (a <= t) {
      emplace_l(a);
    } else {
      min_f += a - t;
      emplace_r(a);
      r.pop();
      emplace_l(t);
    }
  }

  void abs_x_minus_a(const T a) {
    x_minus_a(a);
    a_minus_x(a);
  }

  void cumulative_min() {
    while (!r.empty()) r.pop();
    added_r = 0;
  }

  void rcumulative_min() {
    while (!l.empty()) l.pop();
    added_l = 0;
  }

  void translate(const T a) { sliding_window_minimum(a, a); }

  void sliding_window_minimum(const T a, const T b) {
    assert(a <= b);
    added_l += a;
    added_r += b;
  }

 private:
  T added_l, added_r, min_f;
  std::priority_queue<T> l;
  std::priority_queue<T, std::vector<T>, std::greater<T>> r;

  void emplace_l(const T a) { l.emplace(a - added_l); }
  void emplace_r(const T a) { r.emplace(a - added_r); }

  T top_l() const { return l.empty() ? -inf : l.top() + added_l; }
  T top_r() const { return r.empty() ? inf : r.top() + added_r; }
};

}  // namespace emthrm

#endif  // EMTHRM_DATA_STRUCTURE_SLOPE_TRICK_HPP_

#line 1 "include/emthrm/data_structure/slope_trick.hpp"



#include <cassert>
#include <functional>
#include <limits>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>

namespace emthrm {

template <typename T>
struct SlopeTrick {
  const T inf;

  explicit SlopeTrick(
      const T min_f = 0, const T inf = std::numeric_limits<T>::max())
      : inf(inf), added_l(0), added_r(0), min_f(min_f) {}

  T min() const { return min_f; }
  std::pair<T, T> argmin() const { return {top_l(), top_r()}; }

  template <typename U>
  U f(const U x) {
    U f_x = min_f;
    std::vector<T> tmp;
    for (; top_l() > x; l.pop()) {
      const T t = top_l();
      f_x += t - x;
      tmp.emplace_back(t);
    }
    for (; !tmp.empty(); tmp.pop_back()) {
      emplace_l(tmp.back());
    }
    for (; top_r() < x; r.pop()) {
      const T t = top_r();
      f_x += x - t;
      tmp.emplace_back(t);
    }
    for (; !tmp.empty(); tmp.pop_back()) {
      emplace_r(tmp.back());
    }
    return f_x;
  }

  void constant_function(const T c) { min_f += c; }

  void x_minus_a(const T a) {
    const T t = top_l();
    if (t <= a) {
      emplace_r(a);
    } else {
      min_f += t - a;
      emplace_l(a);
      l.pop();
      emplace_r(t);
    }
  }

  void a_minus_x(const T a) {
    const T t = top_r();
    if (a <= t) {
      emplace_l(a);
    } else {
      min_f += a - t;
      emplace_r(a);
      r.pop();
      emplace_l(t);
    }
  }

  void abs_x_minus_a(const T a) {
    x_minus_a(a);
    a_minus_x(a);
  }

  void cumulative_min() {
    while (!r.empty()) r.pop();
    added_r = 0;
  }

  void rcumulative_min() {
    while (!l.empty()) l.pop();
    added_l = 0;
  }

  void translate(const T a) { sliding_window_minimum(a, a); }

  void sliding_window_minimum(const T a, const T b) {
    assert(a <= b);
    added_l += a;
    added_r += b;
  }

 private:
  T added_l, added_r, min_f;
  std::priority_queue<T> l;
  std::priority_queue<T, std::vector<T>, std::greater<T>> r;

  void emplace_l(const T a) { l.emplace(a - added_l); }
  void emplace_r(const T a) { r.emplace(a - added_r); }

  T top_l() const { return l.empty() ? -inf : l.top() + added_l; }
  T top_r() const { return r.empty() ? inf : r.top() + added_r; }
};

}  // namespace emthrm

Back to top page