Slope Trick

Hai heap và điểm gãy

Hàm $f(x) = \sum_i |x - a_i| + B$ lồi; độ dốc tăng 2 tại mỗi $a_i$. Coi $|x - a| = (a - x)^+ + (x - a)^+$: mỗi số hạng góp một điểm gãy. Lưu:

• heap trái $L$ (lấy lớn nhất): các điểm gãy bên trái đoạn cực tiểu, độ dốc $-|L|$ ở xa bên trái;
• heap phải $R$ (lấy nhỏ nhất): các điểm gãy bên phải, độ dốc $+|R|$ ở xa bên phải;
• $mn$: giá trị nhỏ nhất. Đoạn cực tiểu là $[\text{top}(L), \text{top}(R)]$.

Cộng $(x - a)^+$: nếu $a < \text{top}(L)$ thì giá trị nhỏ nhất tăng $\text{top}(L) - a$; đẩy $a$ vào $L$ rồi chuyển phần tử lớn nhất của $L$ sang $R$. Cộng $(a - x)^+$ thì làm đối xứng. Hai phép này giữ đúng bất biến “mọi phần tử $L$ không lớn hơn mọi phần tử $R$”.

Trong hình, gõ thêm hay bớt số: mỗi điểm gãy làm độ dốc tăng 2. Nửa nhỏ nằm ở $L$ (xanh dương), nửa lớn ở $R$ (xanh lá), đoạn phẳng ở giữa.

Ví dụĐiểm Cân Bằng

Đề. $f$ ban đầu bằng 0. $Q \le 2 \cdot 10^5$ truy vấn: cộng $|x - a| + b$, hoặc in số nguyên $x$ nhỏ nhất làm $f$ nhỏ nhất cùng $f(x)$.

Lời giải. $f$ là hàm lồi tuyến tính từng khúc. Giữ các điểm gãy trong hai heap: L (lớn nhất) chứa điểm gãy bên trái đoạn cực tiểu, R (nhỏ nhất) chứa điểm gãy bên phải, cùng mn là giá trị nhỏ nhất. $b$ cộng thẳng vào mn. Lính canh $-\infty$, $+\infty$ để khỏi kiểm heap rỗng.

Bước 1: cộng $|x - a|$ là cộng hai hàm. Khối đầu là $(x - a)^+$: nếu $a$ nằm bên trái top(L) thì giá trị nhỏ nhất tăng top(L) - a; đẩy $a$ vào L, chuyển phần tử lớn nhất của L sang R. Khối sau đối xứng với $(a - x)^+$.

mn += b;
mn += max(0LL, L.top() - a);
L.push(a);
R.push(L.top()), L.pop();
mn += max(0LL, a - R.top());
R.push(a);
L.push(R.top()), R.pop();

Bất biến “mọi phần tử của L không lớn hơn mọi phần tử của R” được giữ sau mỗi khối, nên đoạn cực tiểu luôn là $[\text{top}(L), \text{top}(R)]$ và mn là giá trị trên đoạn đó.

Bước 2: trả lời. In top(L): điểm nguyên nhỏ nhất của đoạn cực tiểu.

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

const ll INF = 2e18;
priority_queue<ll> L;
priority_queue<ll, vector<ll>, greater<ll>> R;

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

    int q;
    cin >> q;
    L.push(-INF), R.push(INF);
    ll mn = 0;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            ll a, b;
            cin >> a >> b;
            mn += b;
            mn += max(0LL, L.top() - a);
            L.push(a);
            R.push(L.top()), L.pop();
            mn += max(0LL, a - R.top());
            R.push(a);
            L.push(R.top()), R.pop();
        } else {
            cout << L.top() << ' ' << mn << '\n';
        }
    }
}

ChạyInput5
1 4 3
1 8 -1
2
1 2 5
2

Output4 6
4 13

Độ phức tạp: mỗi truy vấn $O(\log Q)$.

Dãy không giảm

DP chọn dãy $B$ không giảm gần $A$ nhất có dạng

Phép $\min_{y \le x}$ san phẳng mọi đoạn dốc lên: heap phải bị xóa sạch. Vậy chỉ cần heap trái. Cộng $|x - a|$ khi không có heap phải: đẩy $a$ vào $L$; nếu $\text{top}(L) > a$ thì chi phí tăng $\text{top}(L) - a$, bỏ đỉnh và đẩy $a$ thêm lần nữa (một bản của $a$ thay cho điểm gãy vừa bị đẩy sang phải rồi bị xóa).

Trong hình, heap trái $L$ có đỉnh tô xanh. Mỗi số nhỏ hơn đỉnh làm tốn $\text{top} - a$ và thay đỉnh bằng $a$.

Dãy tăng nghiêm ngặt đổi về không giảm bằng $a_i - i$: $B_i < B_{i+1}$ nguyên tương đương $B_i - i \le B_{i+1} - (i + 1)$.

Ví dụBậc Thang Nguyên

Đề. $N \le 10^6$, $0 \le A_i \le 2 \cdot 10^9$. Chọn $B$ nguyên tăng nghiêm ngặt, $\sum |A_i - B_i|$ nhỏ nhất.

Lời giải. Trừ $i$ khỏi $A_i$ để đổi dãy tăng nghiêm ngặt thành không giảm, như đã giải thích. $dp_i(x)$ là chi phí nhỏ nhất khi $B_i = x$; mỗi bước lấy min tiền tố rồi cộng $|x - a|$. Phép lấy min tiền tố xóa sạch phía phải ở mỗi bước, nên chỉ cần heap trái.

Đẩy $a$ trước, rồi nếu đỉnh heap vẫn lớn hơn $a$ thì cộng chi phí, bỏ đỉnh và đẩy thêm một bản $a$. Hai bản $a$ thay cho điểm gãy cũ: một bản của $|x - a|$ bên trái, một bản thay cho điểm vừa bị dời sang phải rồi bị xóa.

a -= i;
L.push(a);
if (L.top() > a) {
    ans += L.top() - a;
    L.pop();
    L.push(a);
}

Chi phí tới $10^6 \cdot 2 \cdot 10^9$, dùng long long.

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

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

    int n;
    cin >> n;
    priority_queue<ll> L;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ll a;
        cin >> a;
        a -= i;
        L.push(a);
        if (L.top() > a) {
            ans += L.top() - a;
            L.pop();
            L.push(a);
        }
    }
    cout << ans << '\n';
}

ChạyInput5
5 4 3 8 8

Output5

$O(N \log N)$. Heap ở đây được gọi hàng triệu lần, nên loại heap quan trọng:

priority_queue nhanh hơn multiset khoảng 6 lần: heap trên mảng liền nhau, còn cây đỏ đen cấp phát từng nút. Quy tắc: chỉ cần lấy phần tử lớn nhất thì dùng priority_queue.

Heap hoàn tác

Cùng ý tưởng nhìn theo hướng tham lam: mỗi phần tử heap là một quyết định còn có thể sửa. Bài mua bán mỗi ngày tối đa một cổ phiếu: duyệt giá $p$; nếu giá mua rẻ nhất còn trong heap là $q < p$ thì bán, lãi $p - q$, rồi đẩy $p$ vào heap hai lần. Một bản là “hoàn tác”: nếu sau này gặp giá $p' > p$, lấy bản đó ra nghĩa là bán ở $p'$ thay vì $p$, lãi thêm $p' - p$. Bản còn lại là ngày $p$ làm điểm mua mới. Không bán thì chỉ đẩy $p$ một lần.

Theo slope trick, đây là hàm lợi nhuận lõm theo số cổ phiếu đang giữ; mỗi phần tử heap là một điểm gãy.

Ví dụNhịp Giá

Đề. $N \le 3 \cdot 10^5$ ngày, giá $p_i \le 10^6$. Mỗi ngày mua một, bán một hoặc không làm gì; cuối cùng không giữ cổ phiếu. Lợi nhuận lớn nhất.

Lời giải. Heap nhỏ nhất q chứa các giá có thể là điểm mua. Gặp giá $p$ lớn hơn giá rẻ nhất thì bán ngay, nhưng để lại một bản “hoàn tác” cho phép dời ngày bán về sau.

Giá $p$ lớn hơn top: lãi p - top, bỏ giá đó, rồi đẩy $p$ một lần làm bản hoàn tác. Sau đó (ngoài khối if) đẩy $p$ thêm một lần làm điểm mua của chính ngày đó.

if (!q.empty() && q.top() < p) {
    ans += p - q.top();
    q.pop();
    q.push(p);
}
q.push(p);

Lấy bản hoàn tác ra ở một ngày $p' > p$ về sau nghĩa là bán ở $p'$ thay vì $p$: lãi thêm đúng $p' - p$, cộng với lãi đã tính cho ra lãi của giao dịch dời ngày bán. Bản nào còn lại cuối cùng ứng với không giao dịch, không làm đổi đáp án.

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

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

    int n;
    cin >> n;
    priority_queue<ll, vector<ll>, greater<ll>> q;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll p;
        cin >> p;
        if (!q.empty() && q.top() < p) {
            ans += p - q.top();
            q.pop();
            q.push(p);
        }
        q.push(p);
    }
    cout << ans << '\n';
}

ChạyInput6
5 1 4 2 7 3

Output8

Độ phức tạp: $O(N \log N)$.

Tịnh tiến hai nửa

Phép $g(x) = \min_{y \in [x - b, x + a]} f(y)$ kéo nửa trái sang trái $a$ và nửa phải sang phải $b$, đoạn cực tiểu dài thêm $a + b$. Không sửa từng phần tử: giữ hai độ dời $addL$, $addR$; giá trị thật là giá trị lưu cộng độ dời, và khi đẩy vào thì trừ độ dời đi.

Cộng $|x - a|$ sau đó chia ba trường hợp: $a$ nằm trong đoạn cực tiểu thì đẩy vào cả hai heap; $a$ lệch trái thì giá trị nhỏ nhất tăng $\text{top}(L) - a$, chuyển $\text{top}(L)$ sang $R$ và đẩy $a$ hai lần vào $L$; lệch phải làm đối xứng.

Ví dụDải Hình Nối Liền

Đề. $N \le 10^5$ khoảng $[L_i, R_i]$, dịch ngang với chi phí bằng độ dài dịch. Làm mọi cặp khoảng liên tiếp giao nhau, tổng chi phí nhỏ nhất.

Lời giải. $dp_i(x)$ là chi phí khi khoảng $i$ có đầu trái $x$; đặt $w_i = R_i - L_i$. Khoảng $i - 1$ ở $y$ giao khoảng $i$ ở $x$ khi $y \in [x - w_{i-1}, x + w_i]$. Lấy min trên đoạn đó là dời nửa trái của hàm đi $-w_i$, nửa phải đi $+w_{i-1}$; rồi cộng $|x - L_i|$.

Bước 1: dời cả heap bằng một biến. addL, addR là độ dời của hai heap. Giá trị thật là giá trị lưu cộng độ dời; khi đẩy vào thì trừ độ dời để lưu đúng.

addL -= r[i] - l[i];
addR += r[i - 1] - l[i - 1];
ll a = l[i], lt = L.top() + addL, rt = R.top() + addR;

Bước 2: cộng $|x - L_i|$ theo ba trường hợp. Nằm trong đoạn cực tiểu: đẩy vào cả hai heap. Lệch trái: chi phí tăng lt - a, top(L) chuyển sang R, đẩy $a$ hai lần vào L. Lệch phải đối xứng.

if (a < lt) {
    ans += lt - a;
    L.pop();
    R.push(lt - addR);
    L.push(a - addL), L.push(a - addL);
} else if (a > rt) {
    ans += a - rt;
    R.pop();
    L.push(rt - addL);
    R.push(a - addR), R.push(a - addR);
} else {
    L.push(a - addL), R.push(a - addR);
}

ans là giá trị nhỏ nhất của hàm sau khoảng cuối cùng.

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

const int N = 1e5 + 5;
int n;
ll l[N], r[N];
priority_queue<ll> L;
priority_queue<ll, vector<ll>, greater<ll>> R;

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

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    L.push(l[1]), R.push(l[1]);
    ll addL = 0, addR = 0, ans = 0;
    for (int i = 2; i <= n; i++) {
        addL -= r[i] - l[i];
        addR += r[i - 1] - l[i - 1];
        ll a = l[i], lt = L.top() + addL, rt = R.top() + addR;
        if (a < lt) {
            ans += lt - a;
            L.pop();
            R.push(lt - addR);
            L.push(a - addL), L.push(a - addL);
        } else if (a > rt) {
            ans += a - rt;
            R.pop();
            L.push(rt - addL);
            R.push(a - addR), R.push(a - addR);
        } else {
            L.push(a - addL), R.push(a - addR);
        }
    }
    cout << ans << '\n';
}

ChạyInput3
1 3
6 8
9 12

Output4

Độ phức tạp: $O(N \log N)$.

Gộp hàm trên cây

Trên cây, hàm của một đỉnh là tổng hàm của các con: gộp heap điểm gãy, đổ heap nhỏ vào heap lớn ($O(N \log^2 N)$; heap trái lệch cho $O(N \log N)$). Hàm của một cây con có độ dốc ở xa bên phải đúng bằng số con trực tiếp, nên bỏ đi đúng số điểm gãy lớn nhất cần thiết để biết hình dạng quanh cực tiểu.

Ví dụĐồng Bộ Tín Hiệu

Đề. Cây gốc 1, $N + M \le 3 \cdot 10^5$ đỉnh, $M$ lá là đầu nhận. Đổi độ dài cạnh thành số nguyên không âm với chi phí bằng mức thay đổi, sao cho mọi lá cách gốc bằng nhau. Chi phí nhỏ nhất.

Lời giải. $f_v(x)$ là chi phí nhỏ nhất để mọi lá trong cây con $v$, tính cả cạnh lên cha, cách cha đúng $x$. Lá: $|x - c|$, heap gồm hai bản $c$. Đỉnh trong có $k$ con: gộp, bỏ $k - 1$ điểm gãy lớn nhất (còn độ dốc 1 bên phải), lấy hai điểm lớn nhất $a \ge b$ (đoạn phẳng $[b, a]$) và thay bằng $a + c$, $b + c$: cạnh $c$ dời đoạn phẳng, độ dốc hai bên thành $\pm 1$. Ở gốc bỏ $k$ điểm lớn nhất; $f(0) = \sum c$ và mỗi điểm gãy $p$ còn lại bớt đi $p$, nên đáp án là $\sum c - \sum p$.

Bước 1: xử lý một đỉnh. Đề cho cha có chỉ số nhỏ hơn con, nên duyệt $i$ từ $n + m$ về 2 thì mọi con xong trước cha. Tổng hàm của các con có độ dốc deg[i] ở xa bên phải; bỏ deg[i] - 1 điểm gãy lớn nhất để độ dốc bên phải còn 1.

if (i > n) {
    pq[i].push(c[i]), pq[i].push(c[i]);
} else {
    for (int j = 1; j < deg[i]; j++) pq[i].pop();
    ll a = pq[i].top();
    pq[i].pop();
    ll b = pq[i].top();
    pq[i].pop();
    pq[i].push(a + c[i]), pq[i].push(b + c[i]);
}

Bước 2: gộp vào cha. Đổ heap nhỏ vào heap lớn (swap trước để luôn đổ cái nhỏ). Mỗi điểm gãy chuyển $O(\log n)$ lần, mỗi lần $O(\log n)$.

int p = par[i];
if (pq[p].size() < pq[i].size()) swap(pq[p], pq[i]);
while (!pq[i].empty()) pq[p].push(pq[i].top()), pq[i].pop();

Bước 3: ở gốc. Bỏ deg[1] điểm lớn nhất để độ dốc bên phải về 0; mỗi điểm gãy còn lại làm độ dốc tăng 1 từ $f(0) = \sum c$.

for (int j = 0; j < deg[1]; j++) pq[1].pop();
while (!pq[1].empty()) sum -= pq[1].top(), pq[1].pop();

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

const int N = 3e5 + 5;
int n, m, par[N], deg[N];
ll c[N];
priority_queue<ll> pq[N];

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

    cin >> n >> m;
    ll sum = 0;
    for (int i = 2; i <= n + m; i++) {
        cin >> par[i] >> c[i];
        deg[par[i]]++;
        sum += c[i];
    }
    for (int i = n + m; i >= 2; i--) {
        if (i > n) {
            pq[i].push(c[i]), pq[i].push(c[i]);
        } else {
            for (int j = 1; j < deg[i]; j++) pq[i].pop();
            ll a = pq[i].top();
            pq[i].pop();
            ll b = pq[i].top();
            pq[i].pop();
            pq[i].push(a + c[i]), pq[i].push(b + c[i]);
        }
        int p = par[i];
        if (pq[p].size() < pq[i].size()) swap(pq[p], pq[i]);
        while (!pq[i].empty()) pq[p].push(pq[i].top()), pq[i].pop();
    }
    for (int j = 0; j < deg[1]; j++) pq[1].pop();
    while (!pq[1].empty()) sum -= pq[1].top(), pq[1].pop();
    cout << sum << '\n';
}

ChạyInput1 3
1 1
1 4
1 6

Output5

Độ phức tạp: $O((N + M) \log^2 (N + M))$.