Slope Trick

Quick Revisit

• USE WHEN: DP cost function is convex piecewise-linear and transitions involve adding absolute values or taking prefix-min/max
• INVARIANT: Max-heap stores left-side breakpoints (slopes ≤ 0), min-heap stores right-side breakpoints (slopes ≥ 0); base value tracks the minimum
• TIME: O(n log n) | SPACE: O(n)
• CLASSIC BUG: Forgetting to update the base (minimum) value when a breakpoint crosses from the left heap to the right heap or vice versa
• PRACTICE: 04-ladder-dp

AL-34 | Optimize convex piecewise-linear DP transitions from $O(n\cdot V)$ to $O(n\log n)$ by tracking only the breakpoints where the slope changes -- stored in a priority queue.

Difficulty: [Advanced]Prerequisites: DP -- 1D Introduction, Priority Queue & HeapsCF Rating Range: 1900 -- 2100

Contents

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

---

Intuition

2.1 The Pain

You have a sequence of sensor readings that drifts up and down, and you need to smooth it into a non-decreasing signal while minimizing the total adjustment. The natural DP tracks every possible output value at each position -- and that table is enormous.

Problem: Given an array $a[0..n-1]$, find a non-decreasing array $b[0..n-1]$ that minimizes:

$$\sum _{i=0}^{n-1}|a_i-b_i|$$

The standard DP: let $dp[i][v]$ = minimum cost to make the first $i+1$ elements non-decreasing with $b_i=v$.

$$dp[i][v]=|a_i-v|+\underset{u\le v}{min}dp[i-1][u]$$

The value $v$ ranges over all possible values in the array -- call this range $V$.

Concrete example ($a=[3,1,4]$, values in $\{1,2,3,4\}$):

$v$	$dp[0][v]$	$\underset{u\le v}{min}dp[0]$	$dp[1][v]$	$\underset{u\le v}{min}dp[1]$	$dp[2][v]$
1	2	2	2+0=2	2	2+3=5
2	1	1	1+1=2	2	2+2=4
3	0	0	0+2=2	2	2+1=3
4	1	0	0+3=3	2	2+0=2

Answer: $\underset{v}{min}dp[2][v]=2$ (set $b=[3,3,4]$, cost $0+2+0=2$).

Time complexity: $O(n\cdot V)$. For $n={10}^5$ and $V={10}^9$, this is hopeless.

2.2 The Key Insight

Look at the shape of $dp[i][\cdot ]$ as a function of $v$:

• $dp[0][v]=|v-3|$: a V-shape centered at $3$. Slopes are $-1$ then $+1$.
• After prefix-min ($\underset{u\le v}{min}$): slopes clamp to at most $0$ on the right -- the function flattens.
• Adding $|v-1|$: another V-shape is added -- slopes shift by $\pm 1$ at the new breakpoint.

Each $dp[i][\cdot ]$ is convex and piecewise linear with integer slopes. We never need the full table -- only the breakpoints where the slope changes by $+1$.

A max-heap stores the breakpoints of the "left side" (slopes $\le 0$), and a min-heap stores the breakpoints of the "right side" (slopes $\ge 0$). Each transition (add $|v-a_i|$ then prefix-min) touches $O(1)$ breakpoints plus $O(\log n)$ for heap operations.

Total: $O(n\log n)$ instead of $O(n\cdot V)$.

2.3 Visual Walkthrough

Array: $a=[3,1,4]$. We track the DP function $f(v)$ after each element.

Step 0: Process $a_0=3$. Add $|v-3|$.

  cost
  3 |  .                       Slopes: ..., -1, +1, ...
  2 | . .                      Breakpoints (where slope increases by 1):
  1 |.   .                       Left heap (L):  {3}
  0 +--*--.--->  v               Right heap (R): {3}
    0  1  2  3  4  5             min_cost = 0

The function has slope $-1$ for $v<3$, slope $+1$ for $v>3$. Breakpoint $v=3$ appears once in $L$ (slope goes from $-1$ to $0$) and once in $R$ (slope goes from $0$ to $+1$).

Step 1: Process $a_1=1$. Two sub-steps:

(a) Add $|v-1|$: Slope changes by $-1$ at $v=1$ and $+1$ at $v=1$. Push $1$ into both $L$ and $R$.

  cost                          Before prefix-min:
  4 |.                            L = {3, 1},  R = {1, 3}
  3 | .         .                 Slopes: -2, 0, +2
  2 |  .       .                  (two V-shapes stacked)
  1 |   .   . .
  0 +----*.*------>  v
    0  1  2  3  4  5

(b) Prefix-min ($\underset{u\le v}{min}$): Clamp right side -- all positive slopes become $0$. Equivalent to: pop all of $R$, keep only the minimum, set the right side to flat.

Actually, the operation is: the right slopes are capped at $0$. In breakpoint language: discard all breakpoints in $R$ that exceed $\text{top}(L)$. More precisely: while $\text{top}(L)>\text{top}(R)$, pop from both and push back corrected values.

For our representation: push $1$ to $L$ and $R$. Now $L=\{3,1\}$, $R=\{1,3\}$. Since $\text{top}(L)=3>\text{top}(R)=1$, swap: pop $3$ from $L$, pop $1$ from $R$, push $1$ to $L$ and $3$ to $R$. Actually let's be precise about the algorithm:

After adding $|v-a_i|$: push $a_i$ to $L$, push $a_i$ to $R$. If $\text{top}(L)>\text{top}(R)$: swap the tops.

$L=\{3,1\}$, $R=\{1,3\}$. $\text{top}(L)=3$, $\text{top}(R)=1$. $3>1$, so swap: pop both, push $1\to L$, push $3\to R$. Now $L=\{1,1\}$, $R=\{3,3\}$.

Prefix-min: pop everything from $R$ (discard right breakpoints). $R=\{\}$. Accumulate the cost change into $\text{min\_cost}$.

Wait -- we should track this more carefully. Let me use the standard slope trick formulation.

After Step 1 (add $|v-1|$ + prefix-min):

  cost                          After prefix-min:
  2 |.                            L = {1, 1},  R = {} (empty)
  1 | .                           Slopes: ..., -2, -1, 0, 0, 0, ...
  0 +--*-*----------->  v         The function is flat from v=1 onward.
    0  1  2  3  4  5              min_cost = 2

$f(v)=2$ for $v\ge 1$, increases by $1$ per unit below $v=1$, by $1$ more below $v=1$ (two breakpoints at $1$).

Step 2: Process $a_2=4$. Add $|v-4|$: push $4$ to $L$ and $R$.

$L=\{4,1,1\}$ (max-heap), $R=\{4\}$ (min-heap). $\text{top}(L)=4>\text{top}(R)=4$? No ($4\ngtr 4$), so no swap needed.

  cost
  5 |.
  4 | .                         L = {4, 1, 1},  R = {4}
  3 |  .       .                Slopes: ..., -3, -2, -1, +1, ...
  2 +---*-*-----*---->  v       min_cost = 2
    0  1  2  3  4  5

Answer: $\text{min\_cost}=2$. Correct!

2.4 The Invariant

At every step, the DP cost function $f_i(v)$ is convex and piecewise linear with integer slopes. The max-heap $L$ stores breakpoints on the left (each breakpoint increments the slope by $+1$ going left-to-right, i.e., the slope is one less to its left). The min-heap $R$ stores breakpoints on the right. Together with the tracked minimum value, these fully determine $f_i$.

More precisely, if $L$ contains breakpoints $l_1\ge l_2\ge \dots$ and $R$ contains $r_1\le r_2\le \dots$, the function is:

$$f(v)=\text{min\_val}+\sum _{l_k>v}(l_k-v)+\sum _{r_k<v}(v-r_k)$$

This is convex, piecewise linear, and fully determined by the heaps + the minimum.

2.5 When to Reach for This

Trigger phrases:

• "Minimize total cost to make a sequence non-decreasing (or non-increasing)."
• "Cost function uses absolute values $|a_i-b_i|$."
• "The DP over values is convex and piecewise linear."
• "Value range is huge (${10}^9$) but only $n\le {10}^5$ elements."

Does NOT apply when:

• The cost is quadratic ($(a_i-b_i{)}^2$) -- different technique (isotonic regression).
• The DP function is not convex (e.g., concave or arbitrary shape).
• You need the actual optimal $b$ array, not just the cost (slope trick gives cost; recovering $b$ needs extra bookkeeping).

What the Code Won't Teach You

Reading the implementation, you see two heaps and some push/pop operations. Here's what that code means but doesn't say:

The core idea: represent the function by its slope changes, not its values. Instead of storing $dp[i][x]$ for every $x$ (which could be ${10}^9$ values), observe that $dp[i](\cdot )$ is a piecewise linear convex function. Such a function is completely determined by the points where its slope changes (breakpoints) and its minimum value. That's $O(n)$ data instead of $O(V)$.

Why two priority queues (heaps)? Because the function is convex, its slopes are non-decreasing: $\dots ,-3,-2,-1,0,0,+1,+2,\dots$ The slopes go from negative (left of the minimum) through zero (at the minimum) to positive (right of the minimum). The breakpoints split naturally into:

• Left breakpoints (L, max-heap): where the slope increments on the left side (slopes <= 0). A max-heap because we need fast access to the rightmost left breakpoint (the edge of the minimum region).
• Right breakpoints (R, min-heap): where the slope increments on the right side (slopes >= 0). A min-heap because we need the leftmost right breakpoint.

  ── Diagram A: Piecewise Linear Convex Function & Heap Contents ──

  f(x) with breakpoints at x = 1, 3, 5, 7:

  cost
   6 |\.                          ./
   5 | \.                        ./
   4 |  \.                      ./     Slopes (left to right):
   3 |   \.        ___         ./        -3, -2, -1, 0, +1, +2
   2 |    \.      /   \       ./
   1 |     \.   ./     \.   ./         Breakpoints where slope
   0 +------*--*--------*--*-----> x    changes by +1:
          1  3          5  7
                                       L (max-heap): {3, 1}
        ◄─── left ──►   ◄─ right─►      (slope <= 0 side)
        slopes <= 0   flat  slopes >= 0  R (min-heap): {5, 7}
                                         (slope >= 0 side)
                                       min_val = 0

When does slope trick apply? Look for these ingredients: (1) cost functions involve $|x-a|$ terms, (2) transitions involve prefix-min or suffix-min (monotonicity constraints), and (3) these operations shift or add breakpoints. The hallmark: each step adds $O(1)$ breakpoints and possibly removes some.

The "add $|x-a|$" operation -- one push to each heap. Adding $|x-a|$ to the function creates a V-shape at $x=a$: slope decreases by 1 just left of $a$ (push $a$ to L) and increases by 1 just right of $a$ (push $a$ to R). If this violates the invariant (L's max > R's min), swap the tops -- the overlap cost gets added to min_val.

  ── Diagram B: The "add |x - a|" Operation (a = 4) ──

  BEFORE: f(x)                    |x - 4|:
  cost                            cost
   3 |\.         flat              2 |\.       ./
   2 | \.                          1 | \.   . /
   1 |  \.                         0 +---\-*-/----> x
   0 +---*--*-----------> x              2 4 6
        1  3
  L={3,1} R={}  min=2             V-shape at x = 4

  AFTER: f(x) + |x - 4|
  cost
   5 |\.
   4 | \.             ./
   3 |  \.         . /             L = {3, 1}  ->  push 4  ->  L = {4, 3, 1}
   2 +---*--*-----*./              R = {}      ->  push 4  ->  R = {4}
        1  3     4                 L.top()=4, R.top()=4 -> 4 <= 4 OK
                                   No swap needed.  min_val stays 2.
  Slopes: -2  -1  0  +1
  New breakpoint at x=4 added to both heaps.

  ── Diagram C: Two-Heap Representation ──

       L (max-heap)              R (min-heap)
      ┌────────────┐            ┌────────────┐
      │  top -> 3   │            │  top -> 5   │
      │     / \    │            │     / \    │
      │    1   2   │            │    7   6   │
      └────────────┘            └────────────┘
           │                         │
    Left breakpoints            Right breakpoints
    (slope changes on           (slope changes on
     left of minimum)            right of minimum)

       ◄── all of L ──►  <=  ◄── all of R ──►
            Invariant: max(L) <= min(R)

  Together with min_val, this FULLY describes f(x):

    f(x) = min_val + Σ max(0, lₖ - x)  +  Σ max(0, x - rₖ)
                     lₖ ∈ L                 rₖ ∈ R

  ┌─────────────────────────────────────────────────┐
  │  With lazy offsets (L_offset, R_offset):        │
  │    actual value = stored value + offset          │
  │    push(x): heap.push(x - offset)              │
  │    top():   heap.top() + offset                 │
  │    "shift all by δ": offset += δ  <- O(1)!      │
  └─────────────────────────────────────────────────┘

---

3. STL / API Quick Reference

Function / Class	Header	What it does	Time
priority_queue<T>	<queue>	Max-heap for left breakpoints	$O(\log n)$ push/pop
priority_queue<T, vector<T>, greater<T>>	<queue>	Min-heap for right breakpoints	$O(\log n)$ push/pop
top()	<queue>	Peek at the largest (max-heap) or smallest (min-heap) breakpoint	$O(1)$
push(x)	<queue>	Insert a breakpoint	$O(\log n)$
pop()	<queue>	Remove top breakpoint	$O(\log n)$

Lazy offset trick: Instead of shifting all breakpoints in a heap (e.g., "add $c$ to every element"), maintain a global offset variable and add it when reading/inserting.

---

Implementation (Contest-Ready)

Version A: Make Non-Decreasing (Minimum $\sum |a_i-b_i|$)

Minimal contest template:

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

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

    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;

    // L = max-heap (left breakpoints), R = min-heap (right breakpoints)
    priority_queue<ll> L;
    priority_queue<ll, vector<ll>, greater<ll>> R;
    ll min_cost = 0;

    for (int i = 0; i < n; i++) {
        // Add |v - a[i]|: push a[i] to both heaps
        L.push(a[i]);
        R.push(a[i]);

        // Restore convexity: if left top > right top, swap them
        if (L.top() > R.top()) {
            ll lt = L.top(), rt = R.top();
            L.pop(); R.pop();
            // The swap costs (lt - rt) added to the minimum
            min_cost += lt - rt;
            L.push(rt);
            R.push(lt);
        }

        // Prefix-min: discard all right breakpoints
        // (makes function flat on the right = non-decreasing constraint)
        while (!R.empty()) R.pop();
    }

    cout << min_cost << "\n";
    return 0;
}

Explained version:

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

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

    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;

    // We represent f_i(v) = cost of making a[0..i] non-decreasing
    // with b[i] = v, using its breakpoints.
    //
    // L (max-heap): breakpoints on the left of the minimum.
    //   Each breakpoint p means "slope increases by +1 at v = p"
    //   going left to right (so slope is more negative to the left).
    // R (min-heap): breakpoints on the right of the minimum.
    //   Each breakpoint p means "slope increases by +1 at v = p".
    // min_cost: the minimum value of f_i.
    //
    // Together: f_i(v) = min_cost
    //                   + sum of max(0, l_k - v) for l_k in L
    //                   + sum of max(0, v - r_k) for r_k in R

    priority_queue<ll> L;                                  // max-heap
    priority_queue<ll, vector<ll>, greater<ll>> R;         // min-heap
    ll min_cost = 0;

    for (int i = 0; i < n; i++) {
        // --- Transition: add |v - a[i]| to f ---
        // |v - a[i]| adds a breakpoint at a[i] on both sides:
        //   slope decreases by 1 just left of a[i] (push to L)
        //   slope increases by 1 just right of a[i] (push to R)
        L.push(a[i]);
        R.push(a[i]);

        // The heaps must satisfy: all of L <= all of R.
        // If L.top() > R.top(), the function has a "dip" that
        // violates convexity with the intended partition.
        // Fix: swap the offending tops.  The cost of the swap
        // (the overlap) gets added to min_cost.
        if (L.top() > R.top()) {
            ll lt = L.top(), rt = R.top();
            L.pop(); R.pop();
            min_cost += lt - rt;
            L.push(rt);
            R.push(lt);
        }

        // --- Prefix-min: enforce non-decreasing constraint ---
        // min_{u <= v} f(u) flattens the function for v beyond
        // the minimizer.  All right-side breakpoints are removed.
        while (!R.empty()) R.pop();
    }

    cout << min_cost << "\n";
    return 0;
}

Version B: General Slope Trick Template (with Lazy Offsets)

For problems that combine operations (shift, add absolute value, prefix-min, suffix-min), use lazy offsets on both heaps to avoid touching every element.

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

struct SlopeTrick {
    priority_queue<ll> L;                              // max-heap
    priority_queue<ll, vector<ll>, greater<ll>> R;     // min-heap
    ll min_val = 0;
    ll L_offset = 0, R_offset = 0;

    void push_L(ll x) { L.push(x - L_offset); }
    void push_R(ll x) { R.push(x - R_offset); }
    ll top_L() { return L.empty() ? -1e18 : L.top() + L_offset; }
    ll top_R() { return R.empty() ?  1e18 : R.top() + R_offset; }
    ll pop_L() { ll v = top_L(); L.pop(); return v; }
    ll pop_R() { ll v = top_R(); R.pop(); return v; }

    // Add |v - a| to f(v)
    void add_abs(ll a) {
        push_L(a);
        push_R(a);
        if (top_L() > top_R()) {
            ll l = pop_L(), r = pop_R();
            min_val += l - r;
            push_L(r);
            push_R(l);
        }
    }

    // f(v) <- min_{u <= v} f(u)   (prefix-min: flatten right side)
    void prefix_min() {
        while (!R.empty()) R.pop();
    }

    // f(v) <- min_{u >= v} f(u)   (suffix-min: flatten left side)
    void suffix_min() {
        while (!L.empty()) L.pop();
    }

    // f(v) <- f(v - c)   (shift function right by c)
    void shift_right(ll c) {
        L_offset += c;
        R_offset += c;
    }

    // f(v) <- min_{v-b <= u <= v+a} f(u)
    // Sliding window minimum: expand left by b, right by a.
    void sliding_window(ll a, ll b) {
        L_offset -= b;
        R_offset += a;
    }

    ll get_min() { return min_val; }
};

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

    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;

    SlopeTrick st;
    for (int i = 0; i < n; i++) {
        st.add_abs(a[i]);
        st.prefix_min();
    }

    cout << st.get_min() << "\n";
    return 0;
}

---

Complexity Analysis

Operation	Time	Space
add_abs(a)	$O(\log n)$	$O(1)$ amortized new breakpoints
prefix_min() / suffix_min()	$O(k)$ where $k$ = breakpoints removed	frees memory
shift_right(c)	$O(1)$	$O(1)$
sliding_window(a, b)	$O(1)$	$O(1)$
Full "make non-decreasing"	$O(n\log n)$	$O(n)$ breakpoints total

Why $O(n\log n)$: Each element adds at most 2 breakpoints (one to $L$, one to $R$) and removes at most 2 via the swap. The prefix-min removes breakpoints that are never re-added. Total heap operations across all $n$ elements: $O(n)$. Each costs $O(\log n)$.

Space: At most $O(n)$ breakpoints alive at any time (each element contributes $\le 2$, removals reduce count).

---

Common Patterns

Pattern 1: Make Non-Decreasing ($\sum |a_i-b_i|$)

The canonical problem. Process left to right: add_abs(a[i]) then prefix_min().

SlopeTrick st;
for (int i = 0; i < n; i++) {
    st.add_abs(a[i]);
    st.prefix_min();
}
cout << st.get_min();

Examples: CF 713C -- Sonya and Problem Wihtout a Legend

Pattern 2: Make Non-Increasing

Mirror of Pattern 1. Process left to right: add_abs(a[i]) then suffix_min(). Alternatively, reverse the array and apply Pattern 1.

SlopeTrick st;
for (int i = 0; i < n; i++) {
    st.add_abs(a[i]);
    st.suffix_min();
}
cout << st.get_min();

Pattern 3: Make Strictly Increasing

Reduce to non-decreasing: replace $a_i$ with $a_i-i$. Now "strictly increasing $b$" becomes "non-decreasing $b^{\prime }=b_i-i$" with the same absolute-value costs.

for (int i = 0; i < n; i++) a[i] -= i;
// Now apply Pattern 1

Examples: CF 713C (variant asking for strictly increasing)

Pattern 4: Bounded Modification (Sliding Window Min)

If $|b_i-b_{i-1}|\le d$ (each step can change by at most $d$), replace prefix_min() with sliding_window(d, d):

SlopeTrick st;
for (int i = 0; i < n; i++) {
    st.add_abs(a[i]);
    st.sliding_window(d, d);  // min over [v-d, v+d]
}

This expands the left breakpoints left by $d$ and right breakpoints right by $d$, implementing a sliding window minimum on the function.

Examples: CF 1534F -- Fall Guys

Pattern 5: Weighted Absolute Value ($w_i\cdot |a_i-b_i|$)

If each position has weight $w_i$, push $a_i$ into $L$ and $R$ a total of $w_i$ times. For large $w_i$, store $(value,count)$ pairs in the heap instead.

for (int k = 0; k < w[i]; k++) {
    st.push_L(a[i]);
    st.push_R(a[i]);
}
// Then do the swap-and-fix step

Pattern 6: Combining Two Slope Trick Functions

If $f(v)$ and $g(v)$ are both convex piecewise linear and you want $h(v)=f(v)+g(v)$, merge their breakpoint heaps. This is useful in tree DP where you combine children.

Merge the smaller heap into the larger (small-to-large merging) for $O(n{\log }^{2}n)$ total.

Examples: CF 1534F2 -- Fall Guys (Hard)

---

Contest Cheat Sheet

+-----------------------------------------------------------------+
|                  SLOPE TRICK -- CHEAT SHEET                     |
+-----------------------------------------------------------------+
| WHEN TO USE:                                                    |
|   "Minimize sum |a_i - b_i| subject to monotonicity on b"      |
|   DP over values is convex piecewise-linear with huge V range   |
+-----------------------------------------------------------------+
| REPRESENTATION:                                                 |
|   L = max-heap of left breakpoints (slope changes on left)      |
|   R = min-heap of right breakpoints (slope changes on right)    |
|   min_val = minimum value of the function                       |
|   Invariant: all of L <= all of R                               |
+-----------------------------------------------------------------+
| OPERATIONS:                        TIME:                        |
|   add_abs(a):                      O(log n)                     |
|     push a to L and R                                           |
|     if L.top > R.top: swap tops, add diff to min_val            |
|   prefix_min():                    O(k)                         |
|     clear R (flatten right side)                                |
|   suffix_min():                    O(k)                         |
|     clear L (flatten left side)                                 |
|   shift_right(c):                  O(1)                         |
|     L_offset += c; R_offset += c                                |
|   sliding_window(a,b):             O(1)                         |
|     L_offset -= b; R_offset += a                                |
+-----------------------------------------------------------------+
| REDUCTIONS:                                                     |
|   Strictly increasing:  a[i] -= i, then non-decreasing         |
|   Non-increasing:       suffix_min instead of prefix_min        |
|   Weighted cost w*|.|:  push a[i] w times to each heap         |
+-----------------------------------------------------------------+
| ANSWER: st.get_min() after processing all elements              |
+-----------------------------------------------------------------+

---

Gotchas & Debugging

1. Forgetting the swap after add_abs. After pushing $a_i$ to both heaps, you must check if $L.\text{top}>R.\text{top}$ and swap. Without this, the invariant breaks and the function is no longer convex. Symptom: wrong answer on almost every test.

2. Prefix-min clears $R$, not $L$. A common mix-up: prefix_min makes the function flat to the right (non-decreasing constraint), so right breakpoints are discarded. For non-increasing, clear $L$ instead.

3. Lazy offset accounting. When using L_offset/R_offset, every push must subtract the offset (push(x - offset)) and every top/pop must add it back. Off-by-one in the offset direction causes subtle WA.

4. Strictly increasing needs the $a_i-i$ trick. If you forget to subtract $i$, you solve the non-decreasing version instead. If the problem says "strictly", always transform first.

5. long long everywhere. Costs can accumulate to $O(n\cdot V)\approx {10}^{14}$. Use ll for min_val, offsets, and heap elements.

6. Recovering the optimal array $b$. Slope trick gives only the cost, not the actual $b$ values. To recover $b$, process in reverse: after computing the answer, pop from $L$ to determine each $b_i$ from right to left. This is error-prone; practice it separately.

7. Empty heap access. Before calling L.top() or R.top(), check that the heap is non-empty. In the first iteration $L$ and $R$ each have exactly one element, so this is fine after add_abs, but be careful if your logic differs.

8. Merging heaps (tree DP). When combining slope trick functions from children on a tree, merge the smaller heap into the larger. Using std::priority_queue means popping all of the smaller heap -- there's no built-in merge. Consider __gnu_pbds or a custom mergeable heap for better constants.

9. Stress testing. For small $n$ ($\le 200$) and small $V$ ($\le 100$), compare against the $O(n\cdot V)$ DP table. Generate random arrays and check that both approaches agree.

10. Forgetting to update min_val during the swap. When L.top() > R.top() after pushing, you pop both, swap them, and add the overlap L.top() - R.top() to min_val. The tracked minimum is not automatic from the heaps alone -- it's the third piece of state, and the swap is the only place it moves. Miss this update and every test fails by the accumulated overlap. Write the formula min_val += l - r; as a comment next to the swap so you don't lose it during refactors.

Mental Traps

Trap 1: "Slope trick works for any convex function."

Not quite. Slope trick works specifically for piecewise linear convex functions -- functions made of straight-line segments joined at breakpoints. A smooth convex function like $x^2$ has infinitely many slope changes and can't be represented by a finite set of breakpoints. The key property is: slopes are integers (or at least discrete), so the function is fully described by finitely many breakpoints.

Trap 2: "I need to store the entire function f(x) for all x."

No -- that's the whole point of the technique. You store only the breakpoints (the x-values where the slope changes) in two priority queues, plus the minimum value. Everything else is derived. For a function with $k$ breakpoints, that's $O(k)$ storage instead of $O(V)$.

  WRONG mental model:              CORRECT mental model:
  "Store f(x) for all x"          "Store only breakpoints + min"

  f(x): array of size V           f(x): two heaps + one scalar
  [5, 4, 3, 2, 1, 0, 1, 2, 3]    L (max-heap): {5}
   ^  ^  ^  ^  ^  ^  ^  ^  ^      R (min-heap): {5}
   0  1  2  3  4  5  6  7  8      min_val: 0
   \___ V = 9 entries ___/
                                   That's it. 2 entries + 1 scalar
   Memory: O(V)                    vs O(V) for the full table.
                                   Memory: O(k) breakpoints

Trap 3: "Adding two slope trick functions is complicated."

It's actually the simplest operation conceptually: just merge the two priority queues. If $f$ has breakpoints $\{2,5\}$ and $g$ has breakpoints $\{3,7\}$, then $f+g$ has breakpoints $\{2,3,5,7\}$ -- slopes add, so slope changes (breakpoints) simply combine. The merged min value is $f_{min}+g_{min}$.

  f(x):          g(x):          f(x) + g(x):
    \    /         \  /            \\    //
     \  /           \/              \\  //
      \/                             \\/

  L={2} R={5}    L={3} R={7}     L={2,3} R={5,7}
  min=0          min=0           min=0+0=0

  "Merge" = just pour one heap into the other.
  For tree DP: use small-to-large merging -> O(n log²n) total.

---

Debug Drills

Drill 1: Forgetting to update minimum when popping

What's wrong?

// Make array non-decreasing with minimum total |a[i] - x_i| cost
priority_queue<long long> L; // max-heap, left breakpoints
priority_queue<long long, vector<long long>, greater<>> R; // min-heap, right
long long ans = 0;

for (int i = 0; i < n; i++) {
    L.push(a[i]);
    R.push(a[i]);
    if (L.top() > R.top()) {
        long long l = L.top(), r = R.top();
        L.pop(); R.pop();
        L.push(r);
        R.push(l);
        // BUG: forgot to add (l - r) to ans!
    }
}
cout << ans << endl;

When a breakpoint l from the left heap exceeds r from the right heap and they swap, the function's minimum increases by l - r. Without ans += l - r, the answer underestimates the true cost. Fix: Add ans += l - r; inside the if-block. Minimum-tracking is not automatic from the heaps alone.

Drill 2: Pushing to only one heap instead of both

What's wrong?

// Adding cost |x - a[i]|: should push a[i] to BOTH heaps
for (int i = 0; i < n; i++) {
    L.push(a[i]);
    // BUG: forgot R.push(a[i])!
    if (!R.empty() && L.top() > R.top()) {
        // ... swap logic ...
    }
}

|x - a[i]| introduces two breakpoints -- slope changes from whatever to one less on the left of a[i], and from whatever to one more on the right. Pushing to only L adds only the left slope change, making the function non-convex. Fix: Push a[i] to both L and R.

Drill 3: Lazy offset applied incorrectly

What's wrong?

long long l_offset = 0, r_offset = 0;

void shift(long long delta) {
    l_offset += delta;
    r_offset += delta;
}

void addAbsValue(long long a) {
    L.push(a);      // BUG: should push (a - l_offset)!
    R.push(a);      // BUG: should push (a - r_offset)!
}

With lazy offsets, heap values are stored as (actual - offset) so that heap.top() + offset reconstructs the real breakpoint. Inserting a raw a means its effective value becomes a + offset. Fix: L.push(a - l_offset); and R.push(a - r_offset);. Every read/write must be mirrored through the offset.

---

Self-Test

Before moving to practice problems, verify your understanding:

• [ ] Explain what a "piecewise linear convex function" is and why slope trick represents it with breakpoints instead of storing all values
• [ ] Describe what the two heaps (L and R) store, their heap orientations, and the invariant all of L <= all of R
• [ ] Implement the "add |x - a|" operation on the two-heap representation, including the swap-and-fix step and minimum value update
• [ ] Implement the "shift all breakpoints by δ" operation using the lazy offset trick (O(1) instead of O(n))
• [ ] Walk through the "make array non-decreasing with minimum cost" algorithm on a small example (e.g., a = [3, 1, 4])
• [ ] State the time complexity of slope trick: O(n log n) for n operations, since each element adds O(1) breakpoints and each heap operation is O(log n)
• [ ] Explain why prefix-min corresponds to clearing the right heap R, and suffix-min to clearing the left heap L

---

Practice Problems

CF Rating	What you should be comfortable with
1200	Piecewise-linear convex functions; know that `
1500	Store breakpoints in a priority queue; implement "push left / push right"; implement the basic non-decreasing array problem
1800	Handle shift operations; combine slope trick with prefix-min / suffix-min clipping; solve CSES Increasing Array II and CF 713C
2100	Merge two slope-trick functions (tree DP); handle three-region piecewise-linear functions; solve CF 1534F2 and ABC 217H

#	Problem	Source	Difficulty	Key Idea
1	CF 713C -- Sonya and Problem Wihtout a Legend	CF 713C	1900	Canonical: make non-decreasing, min cost. Direct slope trick or coordinate-compress DP.
2	CF 1534C -- Little Alawn's Puzzle	CF 1534C	1400	Warm-up: cycle counting (not slope trick, but context for 1534F)
3	CF 1534F2 -- Falling Sand (Hard)	CF 1534F2	2100	Slope trick on a tree with merging
4	ABC 217H -- Snuketoon	AtCoder	2100	Slope trick with three regions; absolute value costs from moving
5	CF 1779F -- Xorcerer	CF 1779F	2000	Slope trick on tree structure
6	CF 1Amount -- Stock Trading	CF Blog	2000	Classic slope trick walkthrough problem
7	USACO 2016 -- Fencing the Cows (Plat)	USACO	2000	Monotone sequence with absolute value cost on 2D variant
8	CF 1381C -- Mastermind	CF 1381C	2100	Greedy + matching but slope-trick-like cost analysis
9	JOI 2017 -- Spring Campaign (Hiring)	JOI	2100	Slope trick with sliding window operations
10	CF 1083E -- The Fair Nut and Rectangles	CF 1083E	2100	Convex piecewise-linear DP (CHT also works; slope trick alternative)
11	Increasing Array II	CSES	2100	Make array non-decreasing with minimum cost -- classic slope trick

---

Further Reading

• CF Blog: Slope Trick -- zscoder -- The original and most comprehensive slope trick tutorial.
• CF Blog: Slope Trick Explained -- Nyaan -- Walkthrough with stock trading problem.
• cp-algorithms -- DP Optimizations -- Context on DP speedups.
• Competitive Programmer's Handbook (Laaksonen) -- General DP and convexity background.
• For the CHT alternative to convex DP: see DP -- Convex Hull Trick.
• For divide-and-conquer DP: see DP -- Divide and Conquer Optimization.