Convex Hull Trick

Chuyển tiếp là cực tiểu của các đường thẳng

Viết chuyển tiếp thành $dp_i = \min_j (k_j \cdot x_i + m_j) + c_i$, trong đó $k_j$ và $m_j$ chỉ phụ thuộc $j$, $x_i$ và $c_i$ chỉ phụ thuộc $i$. Mỗi $j$ đã tính xong cho một đường thẳng $y = k_j x + m_j$; hỏi $dp_i$ là hỏi đường nào thấp nhất tại $x_i$. Tập các đường thấp nhất theo $x$ tạo thành một bao dưới lồi: đi từ trái sang phải, hệ số góc của đường đang thấp nhất giảm dần. Một đường nằm hoàn toàn trên bao không bao giờ cần nữa.

Ví dụDãy Chuyển Tiếp Đơn Điệu

Đề. Hai dãy $a$ tăng ngặt ($a_1 = 1$) và $b$ giảm ngặt ($b_n = 0$), $n \le 10^5$. $dp_1 = 0$, $dp_i = \min_{j < i} (dp_j + b_j \cdot a_i)$. In $dp_n$.

Lời giải. Mỗi $j$ cho một đường thẳng $y = b_j \cdot x + dp_j$; tính $dp_i$ là hỏi giá trị nhỏ nhất của các đường tại $x = a_i$. Hệ số góc giảm ngặt khi $j$ tăng, điểm hỏi tăng ngặt: đúng trường hợp hàng đợi hai đầu ở mục sau. Ở đây viết sẵn khung đó.

Bước 1: đường nào vô dụng. Bao lồi lưu trong hai mảng K (hệ số góc), M (tung độ gốc), dùng như hàng đợi hai đầu từ hd tới tl - 1. Đường giữa $y$ vô dụng khi giao điểm của $x$ với $z$ nằm không xa hơn giao điểm của $x$ với $y$; so bằng nhân chéo để khỏi chia, và tích tới $10^{18} \cdot 10^9$ nên dùng __int128.

bool bad(ll x, ll y, ll z) {
    return (__int128)(M[z] - M[x]) * (K[x] - K[y]) <= (__int128)(M[y] - M[x]) * (K[x] - K[z]);
}

Bước 2: thêm đường vào cuối. Ghi đường mới vào ô tl; chừng nào đường áp chót vô dụng thì chép đường mới đè lên nó và lùi tl; cuối cùng tăng tl.

void add(ll k, ll m) {
    K[tl] = k, M[tl] = m;
    while (tl - hd >= 2 && bad(tl - 2, tl - 1, tl)) {
        K[tl - 1] = K[tl], M[tl - 1] = M[tl];
        tl--;
    }
    tl++;
}

Bước 3: hỏi ở đầu. Điểm hỏi tăng dần nên đường tốt nhất chỉ dịch sang phải: bỏ đường đầu khi đường thứ hai đã không tệ hơn tại $x$.

ll get(ll x) {
    while (tl - hd >= 2 && K[hd + 1] * x + M[hd + 1] <= K[hd] * x + M[hd]) hd++;
    return K[hd] * x + M[hd];
}

Bước 4: quy hoạch động. Hỏi tại $a_i$ được $dp_i$, rồi thêm đường của chính $i$ cho các bước sau.

add(b[1], dp[1]);
for (ll i = 2; i <= n; i++) {
    dp[i] = get(a[i]);
    add(b[i], dp[i]);
}

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

const ll N = 1e5 + 5;
ll n, a[N], b[N], dp[N], K[N], M[N], hd, tl;

bool bad(ll x, ll y, ll z) {
    return (__int128)(M[z] - M[x]) * (K[x] - K[y]) <= (__int128)(M[y] - M[x]) * (K[x] - K[z]);
}

void add(ll k, ll m) {
    K[tl] = k, M[tl] = m;
    while (tl - hd >= 2 && bad(tl - 2, tl - 1, tl)) {
        K[tl - 1] = K[tl], M[tl - 1] = M[tl];
        tl--;
    }
    tl++;
}

ll get(ll x) {
    while (tl - hd >= 2 && K[hd + 1] * x + M[hd + 1] <= K[hd] * x + M[hd]) hd++;
    return K[hd] * x + M[hd];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= n; i++) cin >> b[i];
    dp[1] = 0;
    add(b[1], dp[1]);
    for (ll i = 2; i <= n; i++) {
        dp[i] = get(a[i]);
        add(b[i], dp[i]);
    }
    cout << dp[n] << '\n';
}

Input4
1 2 4 7
9 6 3 0

Output57

Mỗi đường vào và ra hàng đợi một lần: $O(n)$.

Hàng đợi hai đầu khi mọi thứ đơn điệu

Khi đường được thêm theo hệ số góc giảm dần (cho bài min), đường mới luôn thấp nhất ở rất xa bên phải, nên được đặt vào cuối bao. Đường áp chót $B$ giữa $A$ (trước nó) và $C$ (đường mới) trở nên vô dụng khi giao điểm của $A$ và $C$ nằm không xa hơn giao điểm của $A$ và $B$ về bên trái: lúc đó trên mọi $x$, hoặc $A$ hoặc $C$ thấp hơn $B$. So hai giao điểm bằng nhân chéo, không chia:

Khi điểm hỏi tăng dần, đường tốt nhất chỉ dịch sang phải trên bao: bỏ đường đầu khi đường thứ hai đã không tệ hơn tại $x$ hiện tại. Mỗi đường vào và ra hàng đợi một lần, tổng $O(n)$. Nếu điểm hỏi không đơn điệu, giữ nguyên bao và tìm kiếm nhị phân đường tốt nhất, $O(\log n)$ mỗi câu. Nếu cả hệ số góc cũng không đơn điệu, dùng cây Li Chao (bài 75).

Ví dụHệ Số Sau Mỗi Trạm

Đề. $n \le 2 \cdot 10^5$ trạm có tải $s_1 \le \dots \le s_n$, hệ số $x \ge f_1 \ge \dots \ge f_n$. Xử lý trạm $i$ với hệ số $c$ tốn $c \cdot s_i$ rồi hệ số thành $f_i$. Phải xử lý trạm $n$; tìm chi phí nhỏ nhất.

Lời giải. $dp_i$ là chi phí nhỏ nhất khi trạm $i$ là trạm xử lý gần nhất: $dp_i = \min(x \cdot s_i,\ \min_{j < i} (dp_j + f_j \cdot s_i))$. Đường ban đầu $(x, 0)$ ứng với chưa xử lý trạm nào, hệ số vẫn là $x$; đường của $j$ có hệ số góc $f_j$, tung độ gốc $dp_j$. Hệ số góc không tăng, điểm hỏi $s_i$ không giảm: dùng khung hàng đợi của ví dụ trước. Đáp án là $dp$ của trạm cuối, vì trạm $n$ bắt buộc phải xử lý.

Bước 1: hai đường cùng hệ số góc. Hệ số góc chỉ không tăng nên có thể bằng nhau. Khi đó chỉ giữ đường có tung độ gốc nhỏ hơn; không xử lý trường hợp này thì bad sẽ nhân với hiệu hệ số góc bằng 0 và cho kết quả sai.

void add(ll k, ll m) {
    if (tl > hd && K[tl - 1] == k) {
        if (M[tl - 1] <= m) return;
        tl--;
    }
    K[tl] = k, M[tl] = m;
    while (tl - hd >= 2 && bad(tl - 2, tl - 1, tl)) {
        K[tl - 1] = K[tl], M[tl - 1] = M[tl];
        tl--;
    }
    tl++;
}

Bước 2: quy hoạch động. bad và get như ví dụ trước.

add(x, 0);
ll dp = 0;
for (ll i = 1; i <= n; i++) {
    dp = get(s[i]);
    add(f[i], dp);
}

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

const ll N = 2e5 + 5;
ll n, x, s[N], f[N], K[N], M[N], hd, tl;

bool bad(ll a, ll b, ll c) {
    return (__int128)(M[c] - M[a]) * (K[a] - K[b]) <= (__int128)(M[b] - M[a]) * (K[a] - K[c]);
}

void add(ll k, ll m) {
    if (tl > hd && K[tl - 1] == k) {
        if (M[tl - 1] <= m) return;
        tl--;
    }
    K[tl] = k, M[tl] = m;
    while (tl - hd >= 2 && bad(tl - 2, tl - 1, tl)) {
        K[tl - 1] = K[tl], M[tl - 1] = M[tl];
        tl--;
    }
    tl++;
}

ll get(ll q) {
    while (tl - hd >= 2 && K[hd + 1] * q + M[hd + 1] <= K[hd] * q + M[hd]) hd++;
    return K[hd] * q + M[hd];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> x;
    for (ll i = 1; i <= n; i++) cin >> s[i];
    for (ll i = 1; i <= n; i++) cin >> f[i];
    add(x, 0);
    ll dp = 0;
    for (ll i = 1; i <= n; i++) {
        dp = get(s[i]);
        add(f[i], dp);
    }
    cout << dp << '\n';
}

Input3 5
1 3 6
4 2 1

Output27

$O(n)$.

Khai triển bình phương

Chi phí kiểu $(h_i - h_j)^2$ hay $(S_i - S_j)^2$ không phải đường thẳng theo $i$, nhưng khai triển ra thì có: $(h_i - h_j)^2 = h_i^2 - 2 h_i h_j + h_j^2$. Phần $h_i^2$ chỉ phụ thuộc $i$, đưa ra ngoài min; phần còn lại là đường có hệ số góc $-2h_j$, tung độ gốc $dp_j + h_j^2$, hỏi tại $x = h_i$. Dãy $h$ tăng thì hệ số góc giảm và điểm hỏi tăng, đúng trường hợp hàng đợi hai đầu. Với chia dãy thành đoạn và chi phí bình phương tổng đoạn, làm tương tự với tổng tiền tố $S$. Giá trị trung gian có thể tới $10^{17}$ nhân $10^6$, nên phép so sánh giao điểm cần __int128.

Ví dụBậc Đá Tăng Dần

Đề. $n \le 2 \cdot 10^5$ bậc với độ cao tăng ngặt tới $10^6$. Nhảy từ $j$ tới $i > j$ tốn $(h_i - h_j)^2 + c$. Tìm chi phí nhỏ nhất từ bậc 1 tới bậc $n$.

Lời giải. Khai triển bình phương: $dp_i = \min_{j < i} (dp_j + h_j^2 - 2h_j h_i) + h_i^2 + c$. Phần trong ngoặc là đường thẳng của $j$ tại $x = h_i$: hệ số góc $-2h_j$ (giảm dần), tung độ gốc $dp_j + h_j^2$. Độ cao tăng ngặt nên không có hai đường cùng hệ số góc, add không cần bước kiểm đó.

Bước 1: khung hàng đợi bad, add, get như ví dụ đầu.

Bước 2: quy hoạch động. Bậc 1 có $dp_1 = 0$. Mỗi bậc hỏi tại $h_i$ (tăng dần), cộng $h_i^2 + c$, rồi thêm đường của chính nó.

add(-2 * h[1], h[1] * h[1]);
for (ll i = 2; i <= n; i++) {
    dp[i] = get(h[i]) + h[i] * h[i] + c;
    add(-2 * h[i], dp[i] + h[i] * h[i]);
}

Đáp án tới khoảng $2 \cdot 10^{17}$.

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

const ll N = 2e5 + 5;
ll n, c, h[N], dp[N], K[N], M[N], hd, tl;

bool bad(ll a, ll b, ll d) {
    return (__int128)(M[d] - M[a]) * (K[a] - K[b]) <= (__int128)(M[b] - M[a]) * (K[a] - K[d]);
}

void add(ll k, ll m) {
    K[tl] = k, M[tl] = m;
    while (tl - hd >= 2 && bad(tl - 2, tl - 1, tl)) {
        K[tl - 1] = K[tl], M[tl - 1] = M[tl];
        tl--;
    }
    tl++;
}

ll get(ll x) {
    while (tl - hd >= 2 && K[hd + 1] * x + M[hd + 1] <= K[hd] * x + M[hd]) hd++;
    return K[hd] * x + M[hd];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> c;
    for (ll i = 1; i <= n; i++) cin >> h[i];
    add(-2 * h[1], h[1] * h[1]);
    for (ll i = 2; i <= n; i++) {
        dp[i] = get(h[i]) + h[i] * h[i] + c;
        add(-2 * h[i], dp[i] + h[i] * h[i]);
    }
    cout << dp[n] << '\n';
}

Input4 3
1 2 5 8

Output28

$O(n)$.

Ví dụChia Bản Thảo

Đề. Nhiều bộ tới hết input. Dãy $n \le 5 \cdot 10^5$ số không âm và hằng số $m$; chia dãy thành đoạn, đoạn có tổng $s$ tốn $s^2 + m$. Tìm tổng nhỏ nhất.

Lời giải. Với tổng tiền tố $S$: $dp_i = S_i^2 + m + \min_{j < i} (dp_j + S_j^2 - 2S_j S_i)$, $dp_0 = 0$. Đường của $j$ có hệ số góc $-2S_j$, tung độ gốc $dp_j + S_j^2$; $j = 0$ cho đường $(0, 0)$. Các số có thể bằng 0 nên $S$ chỉ không giảm: hai đường liên tiếp có thể cùng hệ số góc, nên dùng bản add có kiểm cùng hệ số góc như ví dụ hệ số trạm.

Bước 1: đọc thẳng vào tổng tiền tố, đặt lại hàng đợi mỗi bộ.

for (ll i = 1; i <= n; i++) {
    cin >> S[i];
    S[i] += S[i - 1];
}
hd = tl = 0;
add(0, 0);

Bước 2: quy hoạch động. dp chỉ cần giá trị hiện tại, vì đường của $i$ đã mang theo nó.

ll dp = 0;
for (ll i = 1; i <= n; i++) {
    dp = get(S[i]) + S[i] * S[i] + m;
    add(-2 * S[i], dp + S[i] * S[i]);
}

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

const ll N = 5e5 + 5;
ll n, m, S[N], K[N], M[N], hd, tl;

bool bad(ll a, ll b, ll c) {
    return (__int128)(M[c] - M[a]) * (K[a] - K[b]) <= (__int128)(M[b] - M[a]) * (K[a] - K[c]);
}

void add(ll k, ll v) {
    if (tl > hd && K[tl - 1] == k) {
        if (M[tl - 1] <= v) return;
        tl--;
    }
    K[tl] = k, M[tl] = v;
    while (tl - hd >= 2 && bad(tl - 2, tl - 1, tl)) {
        K[tl - 1] = K[tl], M[tl - 1] = M[tl];
        tl--;
    }
    tl++;
}

ll get(ll x) {
    while (tl - hd >= 2 && K[hd + 1] * x + M[hd + 1] <= K[hd] * x + M[hd]) hd++;
    return K[hd] * x + M[hd];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> n >> m) {
        for (ll i = 1; i <= n; i++) {
            cin >> S[i];
            S[i] += S[i - 1];
        }
        hd = tl = 0;
        add(0, 0);
        ll dp = 0;
        for (ll i = 1; i <= n; i++) {
            dp = get(S[i]) + S[i] * S[i] + m;
            add(-2 * S[i], dp + S[i] * S[i]);
        }
        cout << dp << '\n';
    }
}

Input4 2
1 2 1 3

Output23

Mỗi bộ $O(n)$.

Sắp và bỏ phần tử bị trội

Khi dữ liệu chưa có thứ tự, hãy tìm thứ tự làm chuyển tiếp thành đoạn liên tiếp và làm hệ số góc, điểm hỏi đơn điệu. Với các hình chữ nhật mua theo nhóm, chi phí nhóm là $\max w \cdot \max h$. Một hình nằm gọn trong hình khác (cả $w$ lẫn $h$ không lớn hơn) đi cùng hình kia mà không tốn thêm, nên bỏ nó. Sau khi bỏ, sắp theo $w$ tăng thì $h$ giảm ngặt, và nhóm tối ưu luôn là một đoạn liên tiếp: chi phí đoạn $[j + 1, i]$ là $w_i \cdot h_{j+1}$.

Ví dụGom Lô Đất

Đề. $n \le 5 \cdot 10^4$ lô đất $w_i \times h_i$. Mua một nhóm tốn chiều rộng lớn nhất nhân chiều cao lớn nhất của nhóm. Chia thành các nhóm để tổng chi phí nhỏ nhất.

Lời giải. Một lô vừa hẹp hơn vừa thấp hơn một lô khác thì đi chung nhóm với lô đó miễn phí, nên bỏ được. Sau khi bỏ, sắp theo $w$ tăng thì $h$ giảm ngặt, và một nhóm tốt nhất luôn là một đoạn liên tiếp: nhóm $j + 1..i$ tốn $w_i \cdot h_{j+1}$ (rộng nhất là lô cuối, cao nhất là lô đầu). Vậy $dp_i = \min_{j < i} (dp_j + h_{j+1} \cdot w_i)$: đường của $j$ có hệ số góc $h_{j+1}$ giảm dần, điểm hỏi $w_i$ tăng dần.

Bước 1: bỏ lô bị chứa. Sắp theo $(w, h)$; dùng ngăn xếp: lô mới cao không kém lô trên đỉnh thì lô trên đỉnh nằm gọn trong lô mới (hẹp hơn, thấp hơn), bỏ nó.

sort(p + 1, p + n + 1);
for (ll i = 1; i <= n; i++) {
    while (m && h[m] <= p[i].second) m--;
    m++;
    w[m] = p[i].first;
    h[m] = p[i].second;
}

Bước 2: quy hoạch động. Đường của $j$ là $(h_{j+1}, dp_j)$, thêm ngay sau khi có $dp_j$ (với $j = 0$ là $dp_0 = 0$). Lô cuối không cần thêm đường vì không còn lô nào sau nó.

ll dp = 0;
add(h[1], 0);
for (ll i = 1; i <= m; i++) {
    dp = get(w[i]);
    if (i < m) add(h[i + 1], dp);
}

Chi phí tới $5 \cdot 10^4 \cdot 10^{12}$, dùng long long; so sánh giao điểm trong __int128.

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

const ll N = 5e4 + 5;
ll n, m, w[N], h[N], K[N], M[N], hd, tl;
pair<ll, ll> p[N];

bool bad(ll a, ll b, ll c) {
    return (__int128)(M[c] - M[a]) * (K[a] - K[b]) <= (__int128)(M[b] - M[a]) * (K[a] - K[c]);
}

void add(ll k, ll v) {
    K[tl] = k, M[tl] = v;
    while (tl - hd >= 2 && bad(tl - 2, tl - 1, tl)) {
        K[tl - 1] = K[tl], M[tl - 1] = M[tl];
        tl--;
    }
    tl++;
}

ll get(ll x) {
    while (tl - hd >= 2 && K[hd + 1] * x + M[hd + 1] <= K[hd] * x + M[hd]) hd++;
    return K[hd] * x + M[hd];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> p[i].first >> p[i].second;
    sort(p + 1, p + n + 1);
    for (ll i = 1; i <= n; i++) {
        while (m && h[m] <= p[i].second) m--;
        m++;
        w[m] = p[i].first;
        h[m] = p[i].second;
    }
    ll dp = 0;
    add(h[1], 0);
    for (ll i = 1; i <= m; i++) {
        dp = get(w[i]);
        if (i < m) add(h[i + 1], dp);
    }
    cout << dp << '\n';
}

Input3
2 5
4 3
6 2

Output28

$O(n \log n)$ cho phần sắp, phần còn lại $O(n)$.