m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: Slope Trick
(convex/slope_trick.hpp)

Overview

SlopeTrick<T> maintains a convex piecewise-linear function whose slopes change by integer units. It supports adding hinge and absolute-value functions, translations, sliding-window minima, evaluation, function addition, and min-plus convolution of two slope-trick functions.

The structure stores the breakpoints in two heaps. Most updates take logarithmic time without explicitly constructing the function over its whole domain.

Typical applications include scheduling, sequence adjustment, median costs, and dynamic programs with convex piecewise-linear states.

Complexity Notation

Represented Function

A new object represents f(x) = 0 for every x.

The template parameter must be a signed arithmetic type. long long is recommended for integer problems. All values, breakpoint translations, and intermediate sums must fit in T.

Adding Functions

Method Effect
void add_constant(T c) Adds the constant c.
void add_x_minus_a(T a) Adds max(x - a, 0).
void add_a_minus_x(T a) Adds max(a - x, 0).
void add_abs(T a) Adds abs(x - a).

Each hinge insertion takes amortized $O(\log N)$ time, where N is the current number of stored breakpoints. add_abs inserts two hinges.

Minimum and Argmin

Method Meaning
T minimum() const Minimum function value.
SlopeTrickArgmin<T> argmin() const Closed interval on which the minimum is attained.
int breakpoint_count() const Number of stored unit-slope breakpoints.

argmin() returns SlopeTrickArgmin<T> with optional left and right endpoints. An empty left endpoint means the interval is unbounded below; an empty right endpoint means it is unbounded above.

For the initial constant function, both endpoints are empty.

Translation and Sliding Minimum

shift(delta) replaces the function by

\[g(x) = f(x-\mathrm{delta}).\]

shift(left_delta, right_delta) requires left_delta <= right_delta and computes

\[g(x) = \min_{x-b \le y \le x-a} f(y).\]

This operation shifts the left and right breakpoint heaps independently and takes $O(1)$ time.

The one-sided variants are:

Method Effect
void shift(T delta) Replaces f(x) by f(x - delta).
void shift(T left_delta, T right_delta) Replaces f(x) by a sliding-window minimum.
void prefix_minimum() / void clear_right() Replaces f(x) by min over y <= x of f(y).
void suffix_minimum() / void clear_left() Replaces f(x) by min over y >= x of f(y).

Clearing one side takes linear time in the number of discarded breakpoints.

Evaluation, Merge, and Convolution

T evaluate(T x) const returns f(x) in $O(N)$ time without changing the structure. This is intended mainly for final answers and debugging; slope trick is useful because updates and minimum queries avoid evaluating arbitrary points.

void merge(SlopeTrick other) adds the function represented by other to this function. other is passed by value, so passing an rvalue avoids an extra copy. The operation takes $O((N+M)\log(N+M))$ time in the worst case.

void min_plus_convolve(SlopeTrick other) replaces the represented function by

\[h(x) = \min_y f(y) + g(x-y),\]

where g is the function represented by other. The minimum value becomes f.minimum() + g.minimum(), and the argmin interval is the Minkowski sum of the two argmin intervals. If either side is unbounded on the left or right, the corresponding result side is also unbounded.

SlopeTrick<T> min_plus_convolution(SlopeTrick<T> first, SlopeTrick<T> second) returns the same convolution as a free function. Both APIs take their arguments by value, so moving temporary slope tricks avoids extra copies.

The convolution keeps only slope levels that appear in both functions. Its worst-case running time is $O((N+M)\log(N+M))$.

Example

#include "convex/slope_trick.hpp"
#include <iostream>

int main() {
    m1une::convex::SlopeTrick<long long> slope;
    slope.add_abs(3);
    slope.add_x_minus_a(0);
    slope.shift(-1, 2);

    m1une::convex::SlopeTrick<long long> other;
    other.add_abs(5);
    auto convolved = m1une::convex::min_plus_convolution(slope, other);

    std::cout << convolved.minimum() << "\n";
    auto range = convolved.argmin();
    if (range.left) std::cout << *range.left << "\n";
}

Required by

Verified with

Code

#ifndef M1UNE_CONVEX_SLOPE_TRICK_HPP
#define M1UNE_CONVEX_SLOPE_TRICK_HPP 1

#include <cassert>
#include <functional>
#include <optional>
#include <queue>
#include <type_traits>
#include <utility>
#include <vector>

namespace m1une {
namespace convex {

template <class T>
struct SlopeTrickArgmin {
    std::optional<T> left;
    std::optional<T> right;
};

template <class T>
class SlopeTrick {
    static_assert(std::is_arithmetic_v<T> && std::is_signed_v<T>);

    T _minimum = T();
    T _left_offset = T();
    T _right_offset = T();
    std::priority_queue<T> _left;
    std::priority_queue<T, std::vector<T>, std::greater<T>> _right;

    T left_top() const {
        return _left.top() + _left_offset;
    }

    T right_top() const {
        return _right.top() + _right_offset;
    }

    void push_left(T value) {
        _left.push(value - _left_offset);
    }

    void push_right(T value) {
        _right.push(value - _right_offset);
    }

   public:
    SlopeTrick() = default;

    T minimum() const {
        return _minimum;
    }

    int breakpoint_count() const {
        return int(_left.size() + _right.size());
    }

    SlopeTrickArgmin<T> argmin() const {
        SlopeTrickArgmin<T> result;
        if (!_left.empty()) result.left = left_top();
        if (!_right.empty()) result.right = right_top();
        return result;
    }

    void add_constant(T value) {
        _minimum += value;
    }

    void add_x_minus_a(T a) {
        if (!_left.empty() && left_top() > a) {
            T old = left_top();
            _minimum += old - a;
            _left.pop();
            push_left(a);
            push_right(old);
        } else {
            push_right(a);
        }
    }

    void add_a_minus_x(T a) {
        if (!_right.empty() && right_top() < a) {
            T old = right_top();
            _minimum += a - old;
            _right.pop();
            push_right(a);
            push_left(old);
        } else {
            push_left(a);
        }
    }

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

    void clear_left() {
        _left = std::priority_queue<T>();
    }

    void clear_right() {
        _right = std::priority_queue<T, std::vector<T>, std::greater<T>>();
    }

    void prefix_minimum() {
        clear_right();
    }

    void suffix_minimum() {
        clear_left();
    }

    void shift(T delta) {
        _left_offset += delta;
        _right_offset += delta;
    }

    void shift(T left_delta, T right_delta) {
        assert(left_delta <= right_delta);
        _left_offset += left_delta;
        _right_offset += right_delta;
    }

    T evaluate(T x) const {
        T result = _minimum;
        auto left = _left;
        while (!left.empty()) {
            T breakpoint = left.top() + _left_offset;
            if (breakpoint > x) result += breakpoint - x;
            left.pop();
        }

        auto right = _right;
        while (!right.empty()) {
            T breakpoint = right.top() + _right_offset;
            if (x > breakpoint) result += x - breakpoint;
            right.pop();
        }
        return result;
    }

    void merge(SlopeTrick other) {
        add_constant(other._minimum);
        while (!other._left.empty()) {
            add_a_minus_x(other.left_top());
            other._left.pop();
        }
        while (!other._right.empty()) {
            add_x_minus_a(other.right_top());
            other._right.pop();
        }
    }

    void min_plus_convolve(SlopeTrick other) {
        SlopeTrick result;
        result._minimum = _minimum + other._minimum;

        while (!_left.empty() && !other._left.empty()) {
            result.push_left(left_top() + other.left_top());
            _left.pop();
            other._left.pop();
        }
        while (!_right.empty() && !other._right.empty()) {
            result.push_right(right_top() + other.right_top());
            _right.pop();
            other._right.pop();
        }
        *this = std::move(result);
    }
};

template <class T>
SlopeTrick<T> min_plus_convolution(SlopeTrick<T> first,
                                   SlopeTrick<T> second) {
    first.min_plus_convolve(std::move(second));
    return first;
}

}  // namespace convex
}  // namespace m1une

#endif  // M1UNE_CONVEX_SLOPE_TRICK_HPP
#line 1 "convex/slope_trick.hpp"



#include <cassert>
#include <functional>
#include <optional>
#include <queue>
#include <type_traits>
#include <utility>
#include <vector>

namespace m1une {
namespace convex {

template <class T>
struct SlopeTrickArgmin {
    std::optional<T> left;
    std::optional<T> right;
};

template <class T>
class SlopeTrick {
    static_assert(std::is_arithmetic_v<T> && std::is_signed_v<T>);

    T _minimum = T();
    T _left_offset = T();
    T _right_offset = T();
    std::priority_queue<T> _left;
    std::priority_queue<T, std::vector<T>, std::greater<T>> _right;

    T left_top() const {
        return _left.top() + _left_offset;
    }

    T right_top() const {
        return _right.top() + _right_offset;
    }

    void push_left(T value) {
        _left.push(value - _left_offset);
    }

    void push_right(T value) {
        _right.push(value - _right_offset);
    }

   public:
    SlopeTrick() = default;

    T minimum() const {
        return _minimum;
    }

    int breakpoint_count() const {
        return int(_left.size() + _right.size());
    }

    SlopeTrickArgmin<T> argmin() const {
        SlopeTrickArgmin<T> result;
        if (!_left.empty()) result.left = left_top();
        if (!_right.empty()) result.right = right_top();
        return result;
    }

    void add_constant(T value) {
        _minimum += value;
    }

    void add_x_minus_a(T a) {
        if (!_left.empty() && left_top() > a) {
            T old = left_top();
            _minimum += old - a;
            _left.pop();
            push_left(a);
            push_right(old);
        } else {
            push_right(a);
        }
    }

    void add_a_minus_x(T a) {
        if (!_right.empty() && right_top() < a) {
            T old = right_top();
            _minimum += a - old;
            _right.pop();
            push_right(a);
            push_left(old);
        } else {
            push_left(a);
        }
    }

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

    void clear_left() {
        _left = std::priority_queue<T>();
    }

    void clear_right() {
        _right = std::priority_queue<T, std::vector<T>, std::greater<T>>();
    }

    void prefix_minimum() {
        clear_right();
    }

    void suffix_minimum() {
        clear_left();
    }

    void shift(T delta) {
        _left_offset += delta;
        _right_offset += delta;
    }

    void shift(T left_delta, T right_delta) {
        assert(left_delta <= right_delta);
        _left_offset += left_delta;
        _right_offset += right_delta;
    }

    T evaluate(T x) const {
        T result = _minimum;
        auto left = _left;
        while (!left.empty()) {
            T breakpoint = left.top() + _left_offset;
            if (breakpoint > x) result += breakpoint - x;
            left.pop();
        }

        auto right = _right;
        while (!right.empty()) {
            T breakpoint = right.top() + _right_offset;
            if (x > breakpoint) result += x - breakpoint;
            right.pop();
        }
        return result;
    }

    void merge(SlopeTrick other) {
        add_constant(other._minimum);
        while (!other._left.empty()) {
            add_a_minus_x(other.left_top());
            other._left.pop();
        }
        while (!other._right.empty()) {
            add_x_minus_a(other.right_top());
            other._right.pop();
        }
    }

    void min_plus_convolve(SlopeTrick other) {
        SlopeTrick result;
        result._minimum = _minimum + other._minimum;

        while (!_left.empty() && !other._left.empty()) {
            result.push_left(left_top() + other.left_top());
            _left.pop();
            other._left.pop();
        }
        while (!_right.empty() && !other._right.empty()) {
            result.push_right(right_top() + other.right_top());
            _right.pop();
            other._right.pop();
        }
        *this = std::move(result);
    }
};

template <class T>
SlopeTrick<T> min_plus_convolution(SlopeTrick<T> first,
                                   SlopeTrick<T> second) {
    first.min_plus_convolve(std::move(second));
    return first;
}

}  // namespace convex
}  // namespace m1une
Back to top page