Convex Hull Trick

We wish to solve problems that are of the following form:

Consider a set of functions $\{f_i(x)\}$ on some range $[l,r]$ such that for any two functions $f_i$ and $f_j$, there exists some $m$ such that

• For all $x \in [l,m]$, $f_i(x)\le f_j(x)$
• For all $x \in [m,r]$, $f_i(x)\ge f_j(x)$

Answer queries of the form "what is the maximum/minimum $f_i(x)$ for some given $x\in [l,r]$," given that we have a way of finding $m$ efficiently.

A sufficient (but not necessary) set of conditions:

• All the functions are continuous along the range $[l,r]$.
• No two functions intersect at more than one point.

The most common case is where each $f_i(x)$ is of the form $a_ix+b_i$. Given two lines $f_i(x)=a_ix+b_i$ and $f_j(x)=a_jx+b_j$ such that $a_i<a_j$, their intersection point at $m=\frac{b_i-b_j}{a_j-a_i}$ can be found in $\mathcal{O}(1)$ time. Then it's clear that

• For all $x\le m$, $f_i(x)\ge f_j(x)$.
• For all $x\ge m$, $f_i(x)\le f_j(x)$.

The linear case is known as the convex hull trick because $\max_i(f_i(x))$ as a function of $x$ is concave up (similarly, $\min_i(f_i(x))$ as a function of $x$ is concave down). Check the images from the CF tutorial below if you don't know what this means.

Some possible nonlinear forms of $f_i(x)$:

• $f_i(x)=x^2+a_ix+b_i$

  • Reduces to the linear case, since we can ignore the $x^2$ term when comparing two functions.
• $f_i(x) = \sqrt{x - a_i} + b_i$

  • If this function is defined for all $x\in [l,r]$.
  • Note that when $a_i<a_j$, $\sqrt{x-a_i}-\sqrt{x-a_j}$ is strictly decreasing over the range $x\in [a_j,\infty)$.

In this module, we'll focus on the special case of CHT where "slopes" of functions are monotonic. This specific case is solvable in $\mathcal{O}(N)$ using a std::deque in C++. For the more general $\mathcal{O}(N \log N)$ CHT (which involves a std::multiset), see the LineContainer module.

Tutorial

Solution - The Fair Nut and Rectangles

I won't analyse this problem in great detail since the Codeforces blog in the resources already does so, but essentially, we sort the rectangles by $x$-coordinate and get the following DP recurrence:

Notice how the $-p_j \cdot q_i + dp[j]$ part of the recurrence describes a straight line $y = mx + c$.

Since we sorted the rectangles and no two rectangles are nested, the slopes of the lines we insert are strictly increasing. The query positions are also strictly increasing.

This means we can solve this problem using CHT in $\mathcal{O}(N)$ time! Here is my implementation:

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

struct Rect {
	ll x, y, a;
	bool operator<(Rect B) { return x < B.x; }
};

Rect a[1000001];

Problems