DP -- Convex Hull Trick

Quick Revisit

• USE WHEN: DP transition has the form $dp[i]=\underset{j}{min}(m_j\cdot x_i+b_j)$ — each past state contributes a linear function of the query point
• INVARIANT: The hull/envelope stores only lines that are optimal for some query value; a line is removed when it's never the minimum
• TIME: O(n) monotone queries, O(n log n) arbitrary queries (Li Chao tree) | SPACE: O(n)
• CLASSIC BUG: Integer overflow in the cross-product comparison when removing lines, or using wrong min/max envelope direction
• PRACTICE: 04-ladder-dp

AL-33 | Speed up DP recurrences of the form $dp[i]=\underset{j}{min}(a_j\cdot x_i+b_j)$ from $O(n^2)$ to $O(n\log n)$ (or $O(n)$ with monotone queries) by maintaining an envelope of linear functions.

Difficulty: [Advanced]Prerequisites: DP -- 1D Introduction, Segment TreeCF Rating Range: 2000 -- 2300+

Contents

• Intuition
  • The Pain
  • The Key Insight
  • Visual Walkthrough
  • The Invariant
  • What the Code Won't Teach You
  • When to Reach for This
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
  • Mental Traps
• Self-Test
• Practice Problems
• Further Reading

Contest Frequency: * Specialized -- appears in DP optimization problems (Div 1 C+)

---

Intuition

2.1 The Pain

You're optimizing a pipeline where each stage $i$ incurs a setup cost that depends on some parameter of the previous stage. The natural DP checks every prior stage for each new one -- and that inner loop is killing your runtime.

Consider the recurrence:

$$dp[i]=\underset{j<i}{min}(dp[j]+b[j]\cdot a[i])$$

The naive approach evaluates every $j<i$ for each $i$: $O(n^2)$ transitions. For $n={10}^5$ that is $\sim 5\times {10}^9$ operations -- far too slow.

Concrete example ($n=6$):

$a=[1,3,5,8,12,15]$, $b=[6,5,3,2,1,0]$, $dp[0]=0$.

$i$	Candidates (all $j<i$)	Best $j$	$dp[i]$
1	$0+6\cdot 3=18$	0	18
2	$30,43$	0	30
3	$48,58,54$	0	48
4	$72,78,66,72$	2	66
5	$90,93,75,78,81$	2	75

Total transitions checked: $1+2+3+4+5=15$. For $n={10}^5$ this becomes $\approx 5\times {10}^9$.

2.2 The Key Insight

Fix a past state $j$ and vary the current index $i$. The cost $dp[j]+b[j]\cdot a[i]$ is a linear function of the query point $x=a[i]$:

$$y_j(x)=\underset{\text{slope}}{\underbrace{b[j]}}\cdot x+\underset{\text{intercept}}{\underbrace{dp[j]}}$$

Each transition $dp[j]+b[j]\cdot a[i]$ is a linear function of $a[i]$ -- so we are evaluating lines at query points, and the lower envelope (convex hull) of those lines gives the minimum.

The technique is called the Convex Hull Trick (CHT). When neither slopes nor queries are monotone, we use a Li Chao tree instead.

Lines from our example:

$j$	Line $L_j$: $y=b[j]\cdot x+dp[j]$	slope	intercept
0	$y=6x+0$	6	0
1	$y=5x+18$	5	18
2	$y=3x+30$	3	30
3	$y=2x+48$	2	48
4	$y=x+66$	1	66

Computing $dp[i]$ = evaluating these lines at $x=a[i]$ and taking the minimum. With $O(n)$ lines and $O(n)$ queries, we want to avoid checking every line for every query.

Geometric view -- lower envelope of five lines (minimization):

  y │                            5 lines from states j=0..4:
    │╱                             L0: y = 6x + 0    (steepest)
    │╱  ╲                          L1: y = 5x + 18   <- DOMINATED
    │     ╲  .                     L2: y = 3x + 30
    │      ╲   .                   L3: y = 2x + 48   <- DOMINATED
    │       ╲    .                 L4: y = x  + 66   (flattest)
    │        ╲     .   .
    │         ╲      .    .  .
    │          ╲       .     .  .  .
    │           ╲        .      .  .  .
    ┼─────┼─────┼─────┼─────┼─────┼─────> x
    0     5    10    15    20    25

    LOWER ENVELOPE (the minimum across all lines at each x):
    ════L0════╤════L2════╤════L4═══════════>
             x=10       x=18

    • L1 and L3 are ABOVE the envelope at every x -> discarded
    • dp[i] = envelope value at x = a[i]
    • Only 3 of 5 lines survive -- that's the "hull"

2.3 Visual Walkthrough

We walk through the example, maintaining a hull (deque) of non-redundant lines. At every step: add a line, possibly pop redundant lines, then answer the next query.

Step 1 -- Seed $L_0$, compute $dp[1]$, add $L_1$

$dp[0]=0$ gives line $L_0$: $y=6x$. Query $x=a[1]=3$: only $L_0$ exists, $L_0(3)=18$, so $dp[1]=18$. Add $L_1$: $y=5x+18$. $L_0$ and $L_1$ cross at $x=18$.

  y |
    |          / L0 (slope 6)
    |        /  .
    |      /  .  L1 (slope 5)
    |    / .
    |  /.
    |/.
    +--+-----+--------> x
    0        18

    |----L0----|---L1--->

    Hull: [ L0 , L1 ]

Step 2 -- Compute $dp[2]$, add $L_2$, pop $L_1$

Query $x=a[2]=5$: $L_0(5)=30$, $L_1(5)=43$. Min $=30$, so $dp[2]=30$. Add $L_2$: $y=3x+30$. Is $L_1$ redundant?

• $L_0\cap L_2$ at $x=10$
• $L_0\cap L_1$ at $x=18$

Since $10<18$, the hull transitions from $L_0$ to $L_2$ before it would ever reach $L_1$. $L_1$ is above the envelope everywhere -- pop it.

  y |
    |        / L0
    |      /
    |    / . L1 (popped -- never optimal)
    |  /  .     .
    | / .    .     L2
    |/.    .
    +--+---+---------+---> x
    0     10        18

    Before:  [ L0 , L1 ]
    After:   [ L0 , L2 ]

    |----L0----|---L2-------->
    0         10

Step 3 -- Compute $dp[3]$, add $L_3$

Query $x=a[3]=8$: $L_0(8)=48$, $L_2(8)=54$. Min $=48$, so $dp[3]=48$. Add $L_3$: $y=2x+48$. Is $L_2$ redundant between $L_0$ and $L_3$?

• $L_0\cap L_3$ at $x=12$
• $L_0\cap L_2$ at $x=10$

Since $12>10$, $L_2$ still appears on the hull (wins for $x\in [10,18]$). Keep it.

    |----L0----|--L2--|--L3----->
    0         10     18

    Hull: [ L0 , L2 , L3 ]

Step 4 -- Compute $dp[4]$, add $L_4$, pop $L_3$

Query $x=a[4]=12$: $L_0(12)=72$, $L_2(12)=66$, $L_3(12)=72$. Min $=66$, so $dp[4]=66$. Add $L_4$: $y=x+66$. Is $L_3$ redundant between $L_2$ and $L_4$?

• $L_2\cap L_4$ at $x=18$
• $L_2\cap L_3$ at $x=18$

Since $18\le 18$, $L_3$ never beats both neighbors -- pop it.

    Before:  [ L0 , L2 , L3 ]
    After:   [ L0 , L2 , L4 ]

    |----L0----|---L2---|---L4--->
    0         10       18

Final query: $x=a[5]=15$: $L_2(15)=75$. $dp[5]=75$.

Result: 5 queries answered with $O(n)$ total work -- each line is inserted and removed at most once -- instead of $O(n^2)$ naive evaluation.

Worked Example: Hull State Table Summary

  Lines: L0: y=6x   L1: y=5x+18   L2: y=3x+30   L3: y=2x+48   L4: y=x+66

  | Step | Add | Redundancy check            | Pop? | Hull after         | Query x | Min line | dp  |
  |------|-----|-----------------------------|------|--------------------|---------|----------|-----|
  |  1   | L0  | (first line)                |  --   | [L0]               |    3    | L0(3)=18 |  18 |
  |  2   | L1  | L0∩L1 at x=18, keep        |  --   | [L0, L1]           |    5    | L0(5)=30 |  30 |
  |  3   | L2  | L0∩L2=10 < L0∩L1=18        | L1!  | [L0, L2]           |    8    | L0(8)=48 |  48 |
  |  4   | L3  | L0∩L3=12 > L0∩L2=10, keep  |  --   | [L0, L2, L3]       |   12    | L2(12)=66|  66 |
  |  5   | L4  | L2∩L4=18 <= L2∩L3=18        | L3!  | [L0, L2, L4]       |   15    | L2(15)=75|  75 |

  Walking the hull for query x=12 (Step 4):
    Front of deque: L0(12) = 72
    Next:           L2(12) = 66  <- smaller, pop L0 from front
    Next:           L3(12) = 72  <- larger, stop
    Answer: L2(12) = 66

  Each line entered and left the hull at most once -> O(n) total.

2.4 The Invariant

Invariant. The hull contains only lines that are optimal for at least one query value. Lines are ordered by slope. When a new line is inserted, it can only cause removals from one end of the deque (the end whose adjacent slopes are closest to the new line's slope). Each line is inserted and removed at most once, giving amortized $O(1)$ per operation.

Redundancy test (the "bad" check): Given three consecutive hull lines $L_a,L_b,L_c$, line $L_b$ is redundant iff the intersection $L_a\cap L_c$ occurs at or before $L_a\cap L_b$ -- meaning $L_c$ "takes over" from $L_a$ before $L_b$ ever gets a chance.

Cross-multiply to avoid floating point:

$$(b_c-b_a)(m_a-m_b)\le (b_b-b_a)(m_a-m_c)$$

where $m$ = slope and $b$ = intercept. Use __int128 when values reach ${10}^{18}$.

What the Code Won't Teach You

How to recognize a CHT-eligible recurrence. The template implementations show how to add lines and query, but not how to spot that a DP needs CHT in the first place. The litmus test: can you write the transition as

$$dp[i]=\underset{j}{min}(\underset{\text{intercept}}{\underbrace{f(j)}}+\underset{\text{slope}}{\underbrace{g(j)}}\cdot \underset{\text{query}}{\underbrace{h(i)}})+\text{(terms depending only on }i\text{)}$$

If yes -> CHT applies. If the $j$-terms and $i$-terms are entangled (e.g., $j\cdot i^2$ can't be split into slope$\cdot$query), it doesn't.

The geometric meaning nobody states explicitly. Each completed state $j$ contributes one line $y=g(j)\cdot x+f(j)$. When you process state $i$, you query this family of lines at $x=h(i)$. The answer is the lowest (or highest) line at that $x$-coordinate -- the envelope. CHT is literally "build the envelope, query it."

Why slope monotonicity determines your data structure.

• If slopes $g(j)$ arrive in sorted order and query points $h(i)$ are monotone -> simple deque CHT, $O(n)$ total. The deque pops from both ends and each line enters/leaves once.
• If slopes are sorted but queries aren't -> you still build the hull with a deque but binary-search for the answer: $O(n\log n)$.
• If slopes arrive in arbitrary order -> the deque invariant breaks. You need a Li Chao tree ($O(n\log C)$) which handles any insertion order.

Algebraic transformation step-by-step:

  WORKED EXAMPLE: DP recurrence  ->  CHT form

  Given:  dp[i] = min over j<i of { dp[j] + C[j]² - 2*C[j]*A[i] } + A[i]²

  Step 1: Separate terms by dependence (j only? i only? mixed?)
  ┌────────────────────────────────────────────────────────────┐
  │  dp[i] = min_j { dp[j] + C[j]²    -   2*C[j] * A[i]  }  │
  │                  ╰────────────╯        ╰─────╯   ╰───╯    │
  │                   f(j): j-only       g(j):j-only  h(i):i  │
  │                                      (SLOPE)    (QUERY)   │
  └────────────────────────────────────────────────────────────┘
                  + A[i]²   <- depends only on i -> pull outside min

  Step 2: Identify the linear function of h(i) = A[i]
  ┌────────────────────────────────────────────────────────────┐
  │  For fixed j, the expression inside min_j is:              │
  │                                                            │
  │    y  =  (-2*C[j])  *  x  +  (dp[j] + C[j]²)             │
  │          ╰────────╯         ╰───────────────╯              │
  │           slope m(j)          intercept b(j)               │
  │                                                            │
  │  where  x = A[i]  (the query point)                       │
  └────────────────────────────────────────────────────────────┘

  Step 3: Read off the CHT parameters
    slope[j]     = -2 * C[j]
    intercept[j] = dp[j] + C[j]²
    query[i]     = A[i]
    dp[i]        = CHT_min_query(query[i])  +  A[i]²

With the geometric and algebraic picture clear, here are the practical signals for spotting CHT problems.

2.5 When to Reach for This

Trigger phrases in a problem:

• "DP transition that is a linear function of the current state"
• "minimize (or maximize) $a\cdot x+b$ over a set of stored lines"
• slopes added in sorted order $⟶$ deque/stack CHT ($O(n)$ or $O(n\log n)$)
• queries also monotone $⟶$ deque CHT with front popping ($O(n)$ total)

Counter-examples (when CHT does NOT apply):

Situation	Why not CHT	Use instead
Cost is $b[j]\cdot a[i{]}^2$ (quadratic in $a[i]$)	Not a linear function of query	D&C optimization or Knuth
Slopes and queries both in arbitrary order	Deque/stack CHT needs monotonicity	Li Chao tree ($O(n\log C)$)
Need to undo/rollback line insertions	CHT stack is destructive	Persistent Li Chao tree or offline D&C
Cost depends on $i$ and $j$ in a non-separable way	Cannot split into slope $\cdot$ query + intercept	Other DP optimizations (aliens trick, etc.)

How This Evolved

Many DP recurrences have the form $dp[i]=\underset{j<i}{min}f(j,i)$, and the naive approach evaluates every candidate $j$ -- giving $O(n^2)$ transitions. For a long time, that quadratic inner loop was accepted as unavoidable. The first breakthrough came from noticing that, for certain cost functions, the transition cost $f(j,i)$ can be decomposed into a product of a $j$-dependent term and an $i$-dependent term plus a $j$-dependent constant -- in other words, each candidate $j$ defines a linear function of the query variable $a[i]$. This separability is the key structural insight.

Once you see lines, the optimization follows from computational geometry. Evaluating $n$ lines at $n$ query points naively is $O(n^2)$, but maintaining the lower envelope (convex hull) of those lines lets you answer each query in $O(\log n)$ via binary search -- or even $O(1)$ amortized when queries arrive in sorted order, since a single pointer walks the envelope. The convex hull of lines is maintained on a stack or deque: each new line is inserted in $O(1)$ amortized by popping lines it makes obsolete.

When slopes or queries are not monotone, the stack/deque approach breaks down. The Li Chao tree -- essentially a segment tree over the range of possible query values -- handles fully dynamic insertions and arbitrary-order queries in $O(\log C)$ per operation, completing the toolkit. The evolution from naive $O(n^2)$ to sorted-order $O(n)$ CHT to general $O(n\log C)$ Li Chao tree mirrors a common pattern in competitive programming: first find the mathematical structure, then exploit ordering assumptions, then remove those assumptions with a more general data structure.

---

C++ STL Reference

No dedicated STL container for CHT, but these are used in implementations:

Function / Class	Header	What it does	Time
deque<T>	<deque>	Double-ended queue for CHT line storage; pop front/back $O(1)$	$O(1)$ push/pop
vector<T>	<vector>	Alternative line storage for CHT with binary search queries	$O(1)$ amortized push
__int128	built-in	Avoid overflow in intersection comparisons when values up to ${10}^{18}$	--
numeric_limits<ll>::max()	<limits>	Sentinel for initial DP values	$O(1)$
midpoint(a, b)	<numeric>	C++20 overflow-safe midpoint for Li Chao tree	$O(1)$

---

Implementation (Contest-Ready)

Version A: Convex Hull Trick -- Monotone Slopes + Monotone Queries (Min)

Minimal contest template:

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = 1e18;

struct Line {
    ll a, b; // y = a*x + b
    ll eval(ll x) const { return a * x + b; }
};

struct CHT {
    deque<Line> hull;

    // Is l2 made redundant by l1 and l3?
    bool bad(const Line& l1, const Line& l2, const Line& l3) {
        // l1/l3 intersection x <= l1/l2 intersection x
        // Cross-multiply to avoid floating point:
        // (b3-b1)*(a1-a2) <= (b2-b1)*(a1-a3)
        return (__int128)(l3.b - l1.b) * (l1.a - l2.a)
            <= (__int128)(l2.b - l1.b) * (l1.a - l3.a);
    }

    // Add line with slope >= all existing slopes (sorted insertion)
    void add(ll a, ll b) {
        Line l = {a, b};
        while (hull.size() >= 2 && bad(hull[hull.size()-2], hull[hull.size()-1], l))
            hull.pop_back();
        hull.push_back(l);
    }

    // Query minimum at x; x must be non-decreasing across calls
    ll query(ll x) {
        while (hull.size() >= 2 && hull[0].eval(x) >= hull[1].eval(x))
            hull.pop_front();
        return hull.front().eval(x);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    // Example: dp[i] = min over j<i of (b[j]*a[i] + dp[j])
    // Slopes b[j] must be sorted (add in order).
    // Query points a[i] must be monotone.
    vector<ll> dp(n);
    CHT cht;
    cht.add(b[0], 0); // slope = b[0], intercept = dp[0] = 0
    for (int i = 1; i < n; i++) {
        dp[i] = cht.query(a[i]);
        cht.add(b[i], dp[i]);
    }

    cout << dp[n - 1] << "\n";
    return 0;
}

Explained version:

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = 1e18;

struct Line {
    ll a, b; // represents y = a*x + b
    ll eval(ll x) const { return a * x + b; }
};

struct CHT {
    // We maintain lines forming the lower envelope in a deque.
    // Front = optimal for smallest x, back = optimal for largest x.
    deque<Line> hull;

    // Check if middle line l2 is redundant given l1 (left) and l3 (right).
    // Geometrically: the intersection of l1 and l3 is at or before
    // the intersection of l1 and l2, so l2 never appears on the envelope.
    //
    // Algebra: intersection of l1,l3 at x = (b3-b1)/(a1-a3)
    //          intersection of l1,l2 at x = (b2-b1)/(a1-a2)
    // l2 is bad if (b3-b1)/(a1-a3) <= (b2-b1)/(a1-a2)
    // Cross-multiply (careful with sign -- but since slopes are sorted
    // a1 <= a2 <= a3, denominators have consistent sign).
    // Use __int128 to prevent overflow when values are up to ~10^18.
    bool bad(const Line& l1, const Line& l2, const Line& l3) {
        return (__int128)(l3.b - l1.b) * (l1.a - l2.a)
            <= (__int128)(l2.b - l1.b) * (l1.a - l3.a);
    }

    // Insert a new line. Slopes must be added in non-decreasing order.
    // Pop any line from the back that becomes redundant.
    void add(ll a, ll b) {
        Line l = {a, b};
        while (hull.size() >= 2 && bad(hull[hull.size()-2], hull[hull.size()-1], l))
            hull.pop_back();
        hull.push_back(l);
    }

    // Query: return min(a*x + b) over all inserted lines.
    // x values must be non-decreasing across successive calls.
    // We pop from the front: if the second line is already better than
    // the first at the current x, the first will never be used again
    // (because future x are even larger and the second line only gets
    // more dominant). This gives amortized O(1) per query.
    ll query(ll x) {
        while (hull.size() >= 2 && hull[0].eval(x) >= hull[1].eval(x))
            hull.pop_front();
        return hull.front().eval(x);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Classic problem: CF 319C "Kalila and Dimna in the Logging Industry"
    // dp[i] = min over j<i of (b[j]*a[i] + dp[j])
    // where a[] and b[] come from the problem input.
    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    vector<ll> dp(n, INF);
    dp[0] = 0;

    CHT cht;
    cht.add(b[0], dp[0]);

    for (int i = 1; i < n; i++) {
        dp[i] = cht.query(a[i]);
        cht.add(b[i], dp[i]);
    }

    cout << dp[n - 1] << "\n";
    return 0;
}

Deque maintenance -- adding a line, popping dominated lines:

  BEFORE adding L_new (with largest slope so far):

    Deque: [ La , Lb , Lc ]     (slopes in increasing order)

    y │
      │La╲
      │    ╲  Lb╲
      │      ╲     ╲  Lc╲
      ┼───────p1─────p2──────> x
      │──La───│──Lb──│──Lc──>    (each line optimal in its interval)


  TEST: Does Lc become dominated between Lb and L_new?
    If intersection(Lb, L_new) <= intersection(Lb, Lc)
    then Lc NEVER wins anywhere  ->  pop it!

    y │
      │La╲                     Lb/L_new cross at q
      │    ╲  Lb╲              Lb/Lc   cross at p2
      │      ╲     ╲╱ L_new    q <= p2  ->  Lc is redundant:
      │        ╲  ╱  ╲         L_new takes over before Lc
      │         ╱╲     ╲       ever gets a chance.
      │       ╱   Lc <-(popped!)
      ┼──────q──p2───────────> x


  AFTER popping Lc, repeat test with Lb (maybe it's dominated too):

    Deque: [ La , Lb , L_new ]
    │──La───│──Lb──│──L_new──>

  Each line enters and leaves the deque at most once -> amortized O(1).

Version B: Li Chao Tree (Arbitrary Insertion/Query Order, Min)

Minimal contest template:

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = 1e18;

struct Line {
    ll a = 0, b = INF;
    ll eval(ll x) const { return a * x + b; }
};

struct LiChao {
    int lo, hi;
    struct Node {
        Line line;
        int left = -1, right = -1;
    };
    vector<Node> t;

    LiChao(int lo, int hi) : lo(lo), hi(hi) {
        t.push_back({Line{}, -1, -1});
    }

    void add(Line nl, int v, int l, int r) {
        int mid = l + (r - l) / 2;
        bool lef = nl.eval(l) < t[v].line.eval(l);
        bool mdl = nl.eval(mid) < t[v].line.eval(mid);
        if (mdl) swap(t[v].line, nl);
        if (r - l == 1) return;
        if (lef != mdl) {
            if (t[v].left == -1) {
                t[v].left = (int)t.size();
                t.push_back({Line{}, -1, -1});
            }
            add(nl, t[v].left, l, mid);
        } else {
            if (t[v].right == -1) {
                t[v].right = (int)t.size();
                t.push_back({Line{}, -1, -1});
            }
            add(nl, t[v].right, mid, r);
        }
    }

    void add(ll a, ll b) { add({a, b}, 0, lo, hi); }

    ll query(int x, int v, int l, int r) {
        ll res = t[v].line.eval(x);
        int mid = l + (r - l) / 2;
        if (x < mid && t[v].left != -1)
            res = min(res, query(x, t[v].left, l, mid));
        if (x >= mid && t[v].right != -1)
            res = min(res, query(x, t[v].right, mid, r));
        return res;
    }

    ll query(int x) { return query(x, 0, lo, hi); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    // Li Chao over x-domain [0, MAXVAL)
    const int MAXVAL = 1000001;
    LiChao lct(0, MAXVAL);
    vector<ll> dp(n, INF);
    dp[0] = 0;
    lct.add(b[0], dp[0]);

    for (int i = 1; i < n; i++) {
        dp[i] = lct.query(a[i]);
        lct.add(b[i], dp[i]);
    }

    cout << dp[n - 1] << "\n";
    return 0;
}

Explained version:

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = 1e18;

struct Line {
    ll a = 0, b = INF; // y = a*x + b; default is "infinitely high"
    ll eval(ll x) const { return a * x + b; }
};

// Li Chao Segment Tree: maintains a set of lines and answers
// "what is min(a*x + b) at query point x?" in O(log C) time,
// where C = hi - lo is the coordinate range.
//
// Unlike CHT, there is NO requirement on insertion or query order.
// Handles online, arbitrary-order insertions and queries.
//
// Uses dynamic node creation to avoid allocating the full tree
// when the coordinate range is large (e.g., 0..10^9).
struct LiChao {
    int lo, hi; // coordinate range [lo, hi)

    struct Node {
        Line line;         // the "winner" line at this node's midpoint
        int left = -1;     // index of left child (-1 = not created)
        int right = -1;    // index of right child
    };
    vector<Node> t;

    LiChao(int lo, int hi) : lo(lo), hi(hi) {
        t.push_back({Line{}, -1, -1}); // root node
    }

    // Insert line nl into the subtree rooted at node v, covering [l, r).
    //
    // Key idea (Li Chao's trick):
    //   At each node, store the line that wins at the midpoint.
    //   The other line (loser at mid) might still win in one half.
    //   Recurse into that half only.
    //
    // This guarantees O(log C) per insertion and per query.
    void add(Line nl, int v, int l, int r) {
        int mid = l + (r - l) / 2;
        bool lef = nl.eval(l) < t[v].line.eval(l);   // nl wins at left endpoint?
        bool mdl = nl.eval(mid) < t[v].line.eval(mid); // nl wins at midpoint?

        if (mdl) swap(t[v].line, nl);
        // Now t[v].line wins at mid. nl is the "loser" at mid.
        // But nl might still win in one half.

        if (r - l == 1) return; // leaf -- nothing more to do

        if (lef != mdl) {
            // nl wins at l but loses at mid => nl might win in [l, mid)
            if (t[v].left == -1) {
                t[v].left = (int)t.size();
                t.push_back({Line{}, -1, -1});
            }
            add(nl, t[v].left, l, mid);
        } else {
            // nl loses at l and mid (or wins at both) => check [mid, r)
            if (t[v].right == -1) {
                t[v].right = (int)t.size();
                t.push_back({Line{}, -1, -1});
            }
            add(nl, t[v].right, mid, r);
        }
    }

    void add(ll a, ll b) { add({a, b}, 0, lo, hi); }

    // Query: walk root-to-leaf, take the minimum over all stored lines.
    ll query(int x, int v, int l, int r) {
        ll res = t[v].line.eval(x);
        int mid = l + (r - l) / 2;
        if (x < mid && t[v].left != -1)
            res = min(res, query(x, t[v].left, l, mid));
        if (x >= mid && t[v].right != -1)
            res = min(res, query(x, t[v].right, mid, r));
        return res;
    }

    ll query(int x) { return query(x, 0, lo, hi); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    const int MAXVAL = 1000001;
    LiChao lct(0, MAXVAL);
    vector<ll> dp(n, INF);
    dp[0] = 0;
    lct.add(b[0], dp[0]);

    for (int i = 1; i < n; i++) {
        dp[i] = lct.query(a[i]);
        lct.add(b[i], dp[i]);
    }

    cout << dp[n - 1] << "\n";
    return 0;
}

Deque CHT vs Li Chao Tree

Deque (monotone) CHT: Requires queries to come in sorted order (either all increasing or all decreasing query values). Lines are maintained on a deque; query pops from one end. O(1) amortized per query. Use when DP transitions have monotone query order.

Li Chao Tree: Handles queries in ANY order. Stores lines in a segment tree over the query range. O(log n) per insertion and query. Use when query order is NOT monotone or when you need to handle online queries.

+------------------------------------------------------------+
| CHOOSING:                                                  |
| - Queries monotone? -> Deque CHT (faster, simpler)         |
| - Queries arbitrary? -> Li Chao tree                        |
| - Need to delete lines? -> Neither works well; use          |
|   kinetic segment tree or offline with D&C                 |
+------------------------------------------------------------+

---

Operations Reference

Operation	Time	Space
CHT: add line (sorted slopes)	$O(1)$ amortized	$O(n)$ total
CHT: query min (monotone $x$)	$O(1)$ amortized	--
CHT: query min (arbitrary $x$)	$O(\log n)$	--
Li Chao: add line	$O(\log C)$	$O(n\log C)$
Li Chao: query min at $x$	$O(\log C)$	--
Li Chao: add line segment $[l,r]$	$O({\log }^{2}C)$	$O(n\log C)$

$n$ = number of lines, $C$ = coordinate range size.

---

---

🔍 Why This Works -- Maintaining the Hull Gives Optimal Transitions

The Convex Hull Trick (CHT) works when your DP recurrence looks like:

$$dp[i]=\underset{j}{min}(m_j\cdot x_i+b_j)$$

where each past state $j$ contributes a linear function $f_j(x)=m_j\cdot x+b_j$.

The minimum of a set of linear functions forms a lower convex hull (piecewise linear). When you add a new line, you only need to check if it makes the previous lines on the hull obsolete (remove lines that are no longer part of the minimum envelope).

Key insight: If slopes are sorted (monotone), each line is added/removed at most once from the hull, giving amortized $O(1)$ per insertion. The optimal transition for each query $x_i$ is always on the hull boundary -- you never need interior lines.

---

📐 Where Does the Complexity Come From? -- Amortized O(n) for Sorted Insertions

When lines are inserted in order of decreasing slope (monotone CHT):

• Each line is added to the hull exactly once: $O(1)$ amortized insertion.
• Each line is removed at most once when a newer line makes it obsolete.
• Total insertions + removals over $n$ lines: $O(n)$.

Amortized argument (potential method): Let $\mathrm{\Phi }$ = number of lines currently on the hull. Each insertion adds 1 to $\mathrm{\Phi }$ and may remove $k$ lines (decreasing $\mathrm{\Phi }$ by $k$). Amortized cost = actual cost $O(1+k)$ - $\mathrm{\Delta }\mathrm{\Phi }$ $(k-1)$ = $O(2)$. Summing over $n$ insertions: $O(n)$ total.

For queries, if $x_i$ values are also sorted, each query walks the hull pointer forward -- amortized $O(1)$ per query, total $O(n+q)$.

Problem Patterns & Tricks

Pattern 1: Classic 1D DP Speedup

The bread-and-butter. You have $dp[i]=\underset{j<i}{min}(a_j\cdot x_i+b_j)+c_i$ where $a_j$, $b_j$ depend on $j$ and $x_i$, $c_i$ depend on $i$. Rewrite the recurrence to isolate the linear form, add line $(a_j,b_j)$ after computing $dp[j]$, query at $x_i$ before computing $dp[i]$.

// Recurrence: dp[i] = min over j<i of (slope[j] * x[i] + intercept[j])
// After algebraic rearrangement, add line and query.
cht.add(slope_j, intercept_j);
dp[i] = cht.query(x_i) + extra_cost_i;

Examples: CF 319C -- Kalila and Dimna, CF 631E -- Product Sum

Pattern 2: Slopes Not Sorted -- Use Li Chao Tree

When the slopes $a_j$ are not monotone (e.g., they depend on $dp[j]$ which isn't sorted), the deque-based CHT breaks. Switch to Li Chao tree -- it handles arbitrary insertion order.

LiChao lct(MIN_X, MAX_X);
for (int i = 0; i < n; i++) {
    dp[i] = lct.query(x[i]) + cost[i];
    lct.add(slope(i), dp[i]); // slope(i) in any order
}

Examples: CF 660F -- Bear and Bowling 4, CF 1083E -- The Fair Nut and Rectangles

Pattern 3: Max Instead of Min (Upper Envelope)

Same idea, but maintain the upper envelope. Flip comparisons: either negate all values and use min-CHT, or change <= to >= in the bad check and >= to <= in query popping.

// Negate trick: to maximize a*x+b, minimize (-a)*x+(-b), then negate result.
cht.add(-slope_j, -intercept_j);
dp[i] = -cht.query(x_i);

Examples: CF 1179D -- Fedor Runs for President

Pattern 4: Divide and Conquer + CHT

When the DP has a structure like $dp[i][j]$ with the "monotone minima" property but you also need CHT per layer, combine D&C optimization with CHT. Build CHT on each recursive call's range.

Examples: CF 868F -- Yet Another Minimization Problem

Pattern 5: Li Chao Tree with Line Segments

Sometimes only a segment $[l_i,r_i]$ of line $i$ is valid (e.g., from constraint ranges). Li Chao supports segment insertion in $O({\log }^{2}C)$ by splitting into $O(\log C)$ canonical segments of the tree.

void addSegment(Line nl, int ql, int qr, int v, int l, int r) {
    if (ql >= r || l >= qr) return;
    if (ql <= l && r <= qr) { add(nl, v, l, r); return; }
    int mid = l + (r - l) / 2;
    addSegment(nl, ql, qr, t[v].left, l, mid);
    addSegment(nl, ql, qr, t[v].right, mid, r);
}

Examples: CF 932F -- Escape Through Leaf

Pattern 6: Persistent Li Chao Tree

For tree-DP problems where each node needs the CHT state of its parent: make the Li Chao tree persistent (copy-on-write nodes). Each insertion creates $O(\log C)$ new nodes.

Examples: CF 932F -- Escape Through Leaf (alternate approach), CF 1428G2 -- Lucky Numbers (Hard)

---

Contest Cheat Sheet

+----------------------------------------------------------------+
|              DP CONVEX HULL TRICK -- CHEAT SHEET               |
+----------------------------------------------------------------+
| WHEN TO USE:                                                   |
|   dp[i] = min/max over j of (f(j)*g(i) + h(j))               |
|   Separate j-terms (slope, intercept) from i-terms (query x)  |
+----------------------------------------------------------------+
| CHOOSE YOUR WEAPON:                                            |
|   Slopes sorted + queries monotone => Deque CHT  O(n)         |
|   Slopes sorted + queries arbitrary => Stack CHT O(n log n)   |
|   Anything else (or lazy)           => Li Chao   O(n log C)   |
+----------------------------------------------------------------+
| CHT (MIN, sorted slopes, monotone queries):                    |
|   bad(l1,l2,l3): (__int128)(b3-b1)*(a1-a2)<=(b2-b1)*(a1-a3)  |
|   add: pop back while bad, push_back                           |
|   query: pop front while hull[1](x) <= hull[0](x)             |
+----------------------------------------------------------------+
| LI CHAO (MIN, any order):                                      |
|   add: at mid, winner stays, loser recurses to one child       |
|   query: walk root to leaf, take min of stored lines           |
+----------------------------------------------------------------+
| MAX: negate slopes and intercepts, use min, negate answer      |
+----------------------------------------------------------------+
| WATCH OUT:                                                     |
|   - __int128 for cross-multiply overflow                       |
|   - long long everywhere (slopes * coords can be 10^18)        |
|   - Deque CHT needs BOTH slopes and queries monotone           |
|   - Li Chao domain: set [lo,hi) to cover all query x values   |
+----------------------------------------------------------------+

---

Gotchas & Debugging

1. Overflow in bad() check. Slopes and intercepts can be $O({10}^{18})$; their products overflow long long. Use __int128 for the cross-multiplication comparison. This is the #1 source of WA.

2. Min vs Max confusion. If your DP wants $max$, either flip all signs (negate slope and intercept, query, negate result) or rewrite comparisons. Don't mix.

3. Non-monotone queries with deque CHT. The amortized $O(1)$ query only works if query $x$ values are non-decreasing. If they aren't, you'll pop lines that are still needed for future queries. Symptom: WA on random tests. Fix: use binary search on the hull ($O(\log n)$) or switch to Li Chao.

4. Non-sorted slopes with stack CHT. If slopes aren't added in sorted order, the popping logic is wrong and the hull is invalid. Fix: sort states by slope before insertion (if the DP order allows) or use Li Chao.

5. Li Chao tree coordinate range. You must set [lo, hi) to cover all possible query $x$ values. If queries can be negative, shift coordinates or use a range like $[-{10}^6,{10}^6]$. If the range is huge (${10}^9$), dynamic node creation (as in the implementation above) keeps memory manageable.

6. Empty hull query. Querying before any line is inserted returns garbage. Always insert at least one line (from the base case) before the first query.

7. Floating point. Never use floating point for intersection checks. The __int128 cross-multiply approach is exact and fast.

8. Equal slopes. Two lines with the same slope -- the one with smaller intercept (for min) dominates everywhere. The bad() function handles this correctly, but double-check edge cases if you modify the comparator.

9. Debugging tip: brute force. For small $n$ ($\le 5000$), run the naive $O(n^2)$ DP alongside and compare outputs. Stress test with random data. The most common bug (overflow, wrong monotonicity assumption) shows up quickly.

10. Strict inequality in bad(). When two lines have the same slope but different intercepts, a strict < condition fails to remove the dominated line and the pointer can sit on a suboptimal line. Use <=. When in doubt, use Li Chao tree -- it has no comparator subtlety.

Mental Traps

"CHT only works when slopes are sorted." This is only true for the deque/stack version. The Li Chao tree handles arbitrary insertion order -- slopes can arrive in any sequence. If you dismiss CHT because your slopes aren't monotone, you're leaving a powerful tool on the table. Check whether Li Chao tree applies before giving up.

"I can always use the deque version -- it's simpler and faster." The deque version requires monotone query points (non-decreasing or non-increasing $x$ values across successive queries). If your queries aren't sorted and you use the deque with front-popping, you'll discard lines that are still needed for future (smaller) query values. Symptom: passes small tests, WA on large random tests. If queries aren't monotone, you must use binary search on the hull or switch to Li Chao tree.

"The convex hull stores the lines I inserted." No -- it stores an envelope, which is a subset of your lines. Lines that are dominated everywhere get permanently discarded. You cannot recover them. The hull is lossy by design: that's where the speedup comes from.

  LINE BEING DISCARDED (dominated everywhere):

    y │
      │ L1╲                 L1 and L3 intersect at x = p.
      │     ╲ . L2          Before p: L1 is lower than L2.
      │      .╲    L3       After  p: L3 is lower than L2.
      │     .   ╲ ╱         At ALL x: min(L1, L3) <= L2.
      │    .  ╱  ╳
      │   . ╱  ╱  ╲         L2 is NEVER the minimum
      │  .╱  ╱     ╲        -> discarded from the hull.
      │ ╱  ╱
      ┼───p──────────────> x
      │─L1─│────L3────>      (L2 gone -- envelope is L1 then L3)

---

Debug Drills

Drill 1. Hull pop condition overflow.

struct Line { long long m, c; };
deque<Line> hull;

bool bad(Line l1, Line l2, Line l3) {
    // Check if l2 is unnecessary given l1 and l3
    // Intersection of l1,l3 is at x = (c3-c1)/(m1-m3)
    // l2 is bad if its value at that x >= l1's value
    return (l3.c - l1.c) * (l1.m - l2.m) <= (l2.c - l1.c) * (l1.m - l3.m);
    // BUG: this multiplication can overflow long long!
}

What's wrong?

When slopes and intercepts are up to ~10⁹, the products (l3.c - l1.c) * (l1.m - l2.m) can reach ~10¹⁸, which is within long long range -- but if values reach ~10¹² (e.g., from accumulated DP values), the product overflows 64-bit integers. Fix: Use __int128 for the comparison: (__int128)(l3.c - l1.c) * (l1.m - l2.m) <= (__int128)(l2.c - l1.c) * (l1.m - l3.m). Alternatively, restructure to use floating-point intersection comparison (with care for precision).

Drill 2. Querying the wrong end of the deque.

// Monotone CHT for minimum, queries in increasing order of x
// Lines added with decreasing slopes
long long query(long long x) {
    while (hull.size() > 1) {
        // Compare front two lines at query point x
        if (hull[0].m * x + hull[0].c <= hull[1].m * x + hull[1].c)
            break;
        hull.pop_front();
    }
    return hull.front().m * x + hull.front().c;  // BUG for max queries
}

What's wrong?

This code pops lines from the front when the first line is worse than the second at the current query point. For min queries with increasing x and decreasing slopes, the front should hold the line that becomes optimal earliest, and lines are popped from the front as x increases past their optimality range. The bug: if the problem asks for max instead of min, the comparison <= should be >=, and the envelope is upper, not lower. Mixing up min/max is the most common CHT logic error. Fix: Verify whether you need min or max, and flip the comparison accordingly. Better: parameterize your CHT template with a comparator.

Drill 3. Adding lines in wrong slope order.

// dp[i] = min(dp[j] + b[j] * a[i]) for j < i
// Slopes are b[j], but b[] is NOT sorted!
// Using monotone stack CHT that assumes sorted slopes

void addLine(long long m, long long c) {
    Line l = {m, c};
    while (hull.size() >= 2 && bad(hull[hull.size()-2], hull.back(), l))
        hull.pop_back();
    hull.push_back(l);  // BUG: assumes slopes added in order!
}

What's wrong?

The monotone-stack CHT only works when lines are added in sorted slope order (e.g., increasing slopes for lower envelope). If b[j] values are not monotone, the hull's invariant breaks -- lines may be incorrectly popped, leaving a non-convex "hull." Fix: Either (1) sort the transitions by slope (if the DP order allows it -- often it doesn't), (2) use binary search insertion into a sorted hull (O(n log n)), or (3) switch to a Li Chao tree, which handles arbitrary insertion order naturally.

---

Self-Test

Before moving to practice problems, verify you can do each of these without looking at the notes above:

• [ ] Identify CHT form: Given a DP recurrence, separate terms into slope $\cdot$ query + intercept (terms of $j$ only vs. terms of $i$ only)
• [ ] Implement monotone deque CHT: Write the bad() pruning check, add(), and query() for minimum queries from memory
• [ ] Deque vs Li Chao: Explain when Li Chao tree is needed (arbitrary slopes or non-monotone queries) vs. the simpler deque approach
• [ ] Sketch the envelope: Draw the convex hull of 4-5 lines on paper and identify which lines get discarded as dominated
• [ ] State the complexity: $O(n)$ for sorted slopes + monotone queries; $O(n\log n)$ for sorted slopes + arbitrary queries; $O(n\log C)$ for Li Chao tree
• [ ] Algebraic rearrangement: Transform a DP recurrence like $dp[i]=\underset{j}{min}(dp[j]+c_j^2-2c_j{a}_i)+a_i^2$ into explicit slope, intercept, and query terms

Practice Problems

CF Rating	What You Should Be Comfortable With
1200	Recognize when an O(n²) DP can be algebraically rearranged; understand what "lower envelope of lines" means geometrically
1500	Implement the monotone-stack CHT for sorted slopes + sorted queries (O(n) amortized); solve CSES Monster Game I
1800	Handle non-sorted queries via binary search on the hull (O(n log n)); understand and implement a basic Li Chao segment tree; solve CF 319C
2100	Dynamic Li Chao tree (online insertions + queries); CHT on trees (persistent or DSU-on-tree variants); combine CHT with other DP optimizations; solve CF 932F, CF 1083E

#	Problem	Source	Difficulty	Key Idea
1	CSES -- Monster Game I	CSES	1800	Direct CHT application; sorted slopes, monotone queries
2	CSES -- Monster Game II	CSES	1900	Non-monotone queries; needs binary search or Li Chao
3	CF 319C -- Kalila and Dimna	CF 319C	2000	Classic CHT on DP; the introductory CF problem
4	CF 1083E -- The Fair Nut and Rectangles	CF 1083E	2100	Sort rectangles, CHT on DP with area formula
5	CF 631E -- Product Sum	CF 631E	2100	Rearrange formula into CHT form; prefix sums
6	CF 932F -- Escape Through Leaf	CF 932F	2300	Tree DP + Li Chao (or persistent Li Chao / DSU on tree)
7	CF 1179D -- Fedor Runs for President	CF 1179D	2400	Upper envelope on tree; tricky reformulation
8	AtCoder -- Commuter Pass	AtCoder	1900	BS on answer + greedy (warm-up for envelope thinking)
9	CF 660F -- Bear and Bowling 4	CF 660F	2500	Knuth + CHT layered optimization

---

Further Reading

• cp-algorithms -- Convex Hull Trick -- Canonical reference with proofs.
• cp-algorithms -- Li Chao Tree -- Detailed Li Chao writeup.
• CF Blog: Convex Hull Trick -- Geometry Being Useful -- Excellent tutorial with examples.
• CF Blog: Li Chao Tree -- Implementation-focused post.
• Competitive Programmer's Handbook (Laaksonen), Ch. 26 -- Slope trick and envelope methods.
• For the divide-and-conquer variant: See 11-dp-divide-and-conquer-optimization.md

Related Techniques

• Li Chao Tree -- segment-tree variant for online CHT queries without monotonicity
• DP -- D&C Optimization -- another optimization for DP transitions with monotone structure
• Segment Tree -- Li Chao tree is built on the segment tree framework

---