Build Lab: Dynamic Li Chao Tree & Monotonic Convex Hull Trick Optimizer

1. Architecture & Dual-Engine Verification Invariants

Invariant: Equivalence of Algebraic Envelope & Midpoint Tree

For any sequence of lines $\{L_j(x) = m_j x + b_j\}_{j=1}^{k}$ where $m_1 > m_2 > \dots > m_k$ and queries $x_1 \le x_2 \le \dots \le x_n$:

Monotonic CHT Engine: Maintains a lower-hull deque where consecutive lines $L_a, L_b, L_c$ strictly satisfy $x(L_a, L_b) < x(L_b, L_c)$, advancing the front while $L_0(x_i) \ge L_1(x_i)$.
Extended Li Chao Engine: Supports both global insert_line(m, b) in $O(\log X)$ and bounded-domain insert_segment(m, b, xl, xr) in $O(\log^2 X)$ by decomposing $[x_L, x_R]$ into $O(\log X)$ canonical segment tree intervals and pushing the line down each interval in $O(\log X)$.

2. Dual-Engine System Architecture

flowchart TD Problem["DP Recurrence: dp[i] = f(i) + min_j (m_j * x_i + b_j)"] --> Dispatch{"Are m_j and x_i
Monotonic?"} Dispatch -->|"Yes (m_j decreasing, x_i increasing)"| DequeCHT["MonotonicDequeCHT
O(1) Amortized, __int128 Cross-Product"] Dispatch -->|"No (Arbitrary m_j or x_i)"| LiChao["DynamicLiChaoSegmentTree
O(log X) Global / O(log^2 X) Segment"] DequeCHT --> Verify["Cross-Validate onFrog-3 / Commando Suite"] LiChao --> Verify

3. Engineering Details & Hardware Layout

Contiguous Arena Allocation & Branchless Evaluations

Our MonotonicDequeCHT uses a std::vector<Line> with an explicit head_ index rather than std::deque, keeping all active lines in a single contiguous memory buffer and avoiding std::deque's 512-byte chunk indirection. Our LiChaoEngine pre-reserves a contiguous std::vector<Node> arena so node indices are 32-bit int offsets (8 bytes per child pair instead of 16 bytes for 64-bit pointers).

4. Complexity Matrix

Visualize linear DP transitions dp[i] = min_j(m_j·x_i + b_j) as a lower envelope of lines, popping dominated middle lines when intersect(L1, L3) ≤ intersect(L1, L2).

Preset Speed Step 1 / 8

Custom Input:

Timeline

Invariant & State

Hull stack [L1(y=-x+14), L2(y=-2x+19)] with decreasing slopes m1=-1 > m2=-2. Crossover at x = 5.0.

Active Hull

[L1, L2]

Intersection x(L1, L2)

5.0

Optimal for x < 5

[Step 1] Pushed L1 and L2 onto lower hull; L2 becomes optimal for queries x > 5.0.

Operation	MonotonicDequeCHT	LiChaoEngine (Global Line)	LiChaoEngine (Bounded Segment)
Insert Line / Segment	O(1) amortized	O(log X)	O(log^2 X)
Point Query $\min_j L_j(x)$	O(1) amortized	O(log X)	O(log X)
Total Time for $N$ States	O(N)	O(N log X)	O(N log^2 X)

5. Complete C++20 Build Lab Implementation

#include <vector>
#include <cstdint>
#include <limits>
#include <algorithm>
#include <cassert>

// ============================================================================
// Engine 1: O(1) Amortized Monotonic Deque CHT (Decreasing Slopes, Increasing x)
// ============================================================================
class MonotonicDequeCHT {
public:
    struct Line {
        int64_t m;
        int64_t b;
        int64_t eval(int64_t x) const { return m * x + b; }
    };

private:
    std::vector<Line> hull_;
    std::size_t head_ = 0;

    // Returns true if l2 is made redundant by l1 and l3 (m1 >= m2 >= m3)
    static bool is_redundant(const Line& l1, const Line& l2, const Line& l3) {
        // Intersection(l1, l3) <= Intersection(l1, l2)
        // (l3.b - l1.b) / (l1.m - l3.m) <= (l2.b - l1.b) / (l1.m - l2.m)
        __int128 lhs = static_cast<__int128>(l3.b - l1.b) * (l1.m - l2.m);
        __int128 rhs = static_cast<__int128>(l2.b - l1.b) * (l1.m - l3.m);
        return lhs <= rhs;
    }

public:
    void insert_line(int64_t m, int64_t b) {
        Line nw{m, b};
        // Handle parallel lines with equal slope
        if (hull_.size() > head_ && hull_.back().m == m) {
            if (b >= hull_.back().b) return;
            hull_.pop_back();
        }
        while (hull_.size() - head_ >= 2 &&
               is_redundant(hull_[hull_.size() - 2], hull_.back(), nw)) {
            hull_.pop_back();
        }
        hull_.push_back(nw);
    }

    // Queries minimum value at x (assumes x is non-decreasing across calls)
    int64_t query_monotonic(int64_t x) {
        while (hull_.size() - head_ >= 2 &&
               hull_[head_].eval(x) >= hull_[head_ + 1].eval(x)) {
            ++head_;
        }
        return hull_[head_].eval(x);
    }
};

// ============================================================================
// Engine 2: Dynamic Li Chao Tree with Bounded-Segment Insertion Support
// ============================================================================
class LiChaoEngine {
public:
    static constexpr int64_t INF = std::numeric_limits<int64_t>::max() / 4;

    struct Line {
        int64_t m = 0;
        int64_t b = INF;
        int64_t eval(int64_t x) const { return m * x + b; }
    };

private:
    struct Node {
        Line line;
        int left = -1;
        int right = -1;
    };

    int64_t x_min_, x_max_;
    std::vector<Node> pool_;

    int alloc_node() {
        pool_.push_back(Node{});
        return static_cast<int>(pool_.size()) - 1;
    }

    void push_line(int u, int64_t l, int64_t r, Line nw) {
        int64_t mid = l + (r - l) / 2;
        bool left_win = nw.eval(l) < pool_[u].line.eval(l);
        bool mid_win  = nw.eval(mid) < pool_[u].line.eval(mid);

        if (mid_win) std::swap(pool_[u].line, nw);
        if (l == r) return;

        if (left_win != mid_win) {
            if (pool_[u].left == -1) {
                int c = alloc_node();
                pool_[u].left = c;
            }
            push_line(pool_[u].left, l, mid, nw);
        } else {
            if (pool_[u].right == -1) {
                int c = alloc_node();
                pool_[u].right = c;
            }
            push_line(pool_[u].right, mid + 1, r, nw);
        }
    }

    void add_segment(int u, int64_t l, int64_t r, int64_t ql, int64_t qr, Line nw) {
        if (ql > r || qr < l) return;
        if (ql <= l && r <= qr) {
            push_line(u, l, r, nw);
            return;
        }
        int64_t mid = l + (r - l) / 2;
        if (ql <= mid) {
            if (pool_[u].left == -1) {
                int c = alloc_node();
                pool_[u].left = c;
            }
            add_segment(pool_[u].left, l, mid, ql, qr, nw);
        }
        if (qr > mid) {
            if (pool_[u].right == -1) {
                int c = alloc_node();
                pool_[u].right = c;
            }
            add_segment(pool_[u].right, mid + 1, r, ql, qr, nw);
        }
    }

    int64_t query(int u, int64_t l, int64_t r, int64_t x) const {
        if (u == -1) return INF;
        int64_t ans = pool_[u].line.eval(x);
        if (l == r) return ans;
        int64_t mid = l + (r - l) / 2;
        if (x <= mid) return std::min(ans, query(pool_[u].left, l, mid, x));
        return std::min(ans, query(pool_[u].right, mid + 1, r, x));
    }

public:
    LiChaoEngine(int64_t x_min, int64_t x_max) : x_min_(x_min), x_max_(x_max) {
        pool_.reserve(131072);
        alloc_node();
    }

    void insert_line(int64_t m, int64_t b) {
        push_line(0, x_min_, x_max_, Line{m, b});
    }

    void insert_segment(int64_t m, int64_t b, int64_t xl, int64_t xr) {
        add_segment(0, x_min_, x_max_, xl, xr, Line{m, b});
    }

    int64_t query(int64_t x) const {
        return query(0, x_min_, x_max_, x);
    }
};

// Verification on Frog 3: dp[i] = C + h[i]^2 + min_{j < i} (-2*h[j]*h[i] + dp[j] + h[j]^2)
int64_t solve_frog3_verified(const std::vector<int64_t>& h, int64_t C) {
    MonotonicDequeCHT cht;
    LiChaoEngine lichao(0, h.back());

    int64_t dp_cur = 0;
    cht.insert_line(-2 * h[0], h[0] * h[0]);
    lichao.insert_line(-2 * h[0], h[0] * h[0]);

    for (std::size_t i = 1; i < h.size(); ++i) {
        int64_t v1 = C + h[i] * h[i] + cht.query_monotonic(h[i]);
        int64_t v2 = C + h[i] * h[i] + lichao.query(h[i]);
        assert(v1 == v2);
        dp_cur = v1;

        int64_t m = -2 * h[i];
        int64_t b = dp_cur + h[i] * h[i];
        cht.insert_line(m, b);
        lichao.insert_line(m, b);
    }
    return dp_cur;
}

Production Pitfall — Equal Slopes in Monotonic CHT

If two states $j_1 < j_2$ produce the exact same slope $m_{j_1} = m_{j_2}$, the denominator $(m_1 - m_2)$ in the intersection formula vanishes! In __int128 cross-multiplication, $(b_2 - b_1) \cdot 0$ becomes $0$, which can leave a strictly dominated parallel line on the hull. Always check hull_.back().m == m before cross-multiplication: if the new intercept $b$ is worse, discard the new line; if it is strictly better, pop the old parallel line before running the hull redundancy loop.