Line Container (based on kactl)
(src/datastructure/LineContainer.hpp)

• View this file on GitHub
• Last update: 2023-01-12 22:28:24+09:00
• Include: #include "src/datastructure/LineContainer.hpp"

概要

直線 $f(x) = ax + b$ の追加及びある $x$ での最小値（最大値）クエリを効率的に処理するデータ構造． Convex Hull Trick と異なり，追加する直線の傾きの単調性は問わない． 実装は kactl から． 実数での処理を行う際にはコメントにある注意に沿って適宜書き換える必要がある．

メンバ関数	効果	時間計算量
add(k, m)	直線 $f(x) = kx + m$ を追加する.	全体 $O(n \log n)$
query(x)	$x$ における最小値を求める.	クエリ $O(\log n)$

問題例

• TOKI Regular Open Contest #22 F. MCD
  • 2 乗和は Slope Optimization．
• AtCoder Beginner Contest 244 H - Linear Maximization
  • 実数での処理．

Verified with

• test/yosupo/line_add_get_min.test.cpp

Code

#pragma once
#include <cassert>
#include <climits>
#include <iterator>
#include <set>

struct Line {
    mutable long long k, m, p;
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(long long x) const { return p < x; }
};

template <bool isMin = true> struct LineContainer : std::multiset<Line, std::less<>> {
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    const long long inf = LLONG_MAX / 2;
    long long div(long long a, long long b) {  // floored division
        return a / b - ((a ^ b) < 0 && a % b);
    }
    bool isect(iterator x, iterator y) {
        if (y == end()) {
            x->p = inf;
            return false;
        }
        if (x->k == y->k)
            x->p = x->m > y->m ? inf : -inf;
        else
            x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(long long k, long long m) {
        if (isMin) k = -k, m = -m;
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
    }
    long long query(long long x) {
        assert(!empty());
        auto l = *lower_bound(x);
        long long s = 1;
        if (isMin) s = -1;
        return s * (l.k * x + l.m);
    }
};

#line 2 "src/datastructure/LineContainer.hpp"
#include <cassert>
#include <climits>
#include <iterator>
#include <set>

struct Line {
    mutable long long k, m, p;
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(long long x) const { return p < x; }
};

template <bool isMin = true> struct LineContainer : std::multiset<Line, std::less<>> {
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    const long long inf = LLONG_MAX / 2;
    long long div(long long a, long long b) {  // floored division
        return a / b - ((a ^ b) < 0 && a % b);
    }
    bool isect(iterator x, iterator y) {
        if (y == end()) {
            x->p = inf;
            return false;
        }
        if (x->k == y->k)
            x->p = x->m > y->m ? inf : -inf;
        else
            x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(long long k, long long m) {
        if (isMin) k = -k, m = -m;
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
    }
    long long query(long long x) {
        assert(!empty());
        auto l = *lower_bound(x);
        long long s = 1;
        if (isMin) s = -1;
        return s * (l.k * x + l.m);
    }
};

Back to top page