Slope Trick

傾きが整数で、整数の点でだけ折れ曲がる凸関数 $f(x)$ を、「最小値」「最小値をとる区間より左で、傾きが 1 ずつ変わる点の集合 $L$」「右で傾きが 1 ずつ変わる点の集合 $R$」で表します。 $L$ と $R$ をヒープで持つと、DP の遷移でよく出る操作がそれぞれ $O(\log N)$ でできます（ $N$ は足した関数の個数）。最初は $f(x) = 0$ です。

• add_all(a): $f(x) \gets f(x) + a$。 $O(1)$
• add_x_minus_a(a): $f(x) \gets f(x) + \max(0, x - a)$
• add_a_minus_x(a): $f(x) \gets f(x) + \max(0, a - x)$
• add_abs(a): $f(x) \gets f(x) + \lvert x - a \rvert$
• clear_right(): $f(x) \gets \min_{y \le x} f(y)$（右側を平らにする）。 $O(1)$
• clear_left(): $f(x) \gets \min_{y \ge x} f(y)$（左側を平らにする）。 $O(1)$
• shift(a, b): $f(x) \gets \min_{x - b \le y \le x - a} f(y)$（ $a \le b$）。shift(a) は $f(x) \gets f(x - a)$ の平行移動。 $O(1)$
• min_f: $f$ の最小値
• top_l(), top_r(): $f$ が最小になる $x$ の区間の左端と右端（端がなければ $\mp \mathrm{INF}$）。 $O(1)$
• get(x): $f(x)$。ヒープの中身を全部見るので $O(N)$

例（数列 $a$ の各項を変えて広義単調増加にするときの、変化量 $\sum \lvert a_i - b_i \rvert$ の最小値）: $f_i(x)$ を「 $b_i = x$ のときの最小値」とすると、 $f_i(x) = \min_{y \le x} f_{i - 1}(y) + \lvert x - a_i \rvert$ です。

st = SlopeTrick()
for x in a:
    st.clear_right()
    st.add_abs(x)
print(st.min_f)

コード

from heapq import heappush, heappop


class SlopeTrick:
    # 区分線形な凸関数 f(x) を持つ（最初は f(x) = 0）
    INF = 1 << 62

    def __init__(self):
        self.min_f = 0
        self.L = []  # 最小値をとる区間より左の、傾きが 1 変わる点（-x を入れた最小ヒープ）
        self.R = []  # 最小値をとる区間より右の、傾きが 1 変わる点
        self.add_l = 0  # L の全要素に足す値
        self.add_r = 0  # R の全要素に足す値

    def _push_l(self, a):
        heappush(self.L, -(a - self.add_l))

    def _push_r(self, a):
        heappush(self.R, a - self.add_r)

    def _pop_l(self):
        return -heappop(self.L) + self.add_l

    def _pop_r(self):
        return heappop(self.R) + self.add_r

    def top_l(self):
        # f が最小になる x の左端（なければ -INF）
        return -self.L[0] + self.add_l if self.L else -self.INF

    def top_r(self):
        # f が最小になる x の右端（なければ INF）
        return self.R[0] + self.add_r if self.R else self.INF

    def add_all(self, a):
        # f(x) += a
        self.min_f += a

    def add_x_minus_a(self, a):
        # f(x) += max(0, x - a)
        self.min_f += max(0, self.top_l() - a)
        self._push_l(a)
        self._push_r(self._pop_l())

    def add_a_minus_x(self, a):
        # f(x) += max(0, a - x)
        self.min_f += max(0, a - self.top_r())
        self._push_r(a)
        self._push_l(self._pop_r())

    def add_abs(self, a):
        # f(x) += |x - a|
        self.add_x_minus_a(a)
        self.add_a_minus_x(a)

    def clear_right(self):
        # f(x) を min_{y <= x} f(y) にする（右側を平らにする）
        self.R = []
        self.add_r = 0

    def clear_left(self):
        # f(x) を min_{y >= x} f(y) にする（左側を平らにする）
        self.L = []
        self.add_l = 0

    def shift(self, a, b=None):
        # f(x) を min_{x - b <= y <= x - a} f(y) にする（b を省略すると f(x - a) に平行移動）
        if b is None:
            b = a
        self.add_l += a
        self.add_r += b

    def get(self, x):
        # f(x)。O(ヒープの大きさ)
        res = self.min_f
        for l in self.L:
            res += max(0, -l + self.add_l - x)
        for r in self.R:
            res += max(0, x - r - self.add_r)
        return res