DP kết hợp cấu trúc dữ liệu

Rất nhiều công thức quy hoạch động có dạng "$dp[i]$ bằng min, max hoặc tổng của $dp[j]$ trên một tập $j$ thỏa điều kiện": $j$ nằm trong một cửa sổ, $a[j]<a[i]$, $j$ thuộc đoạn $[L_i,R_i]$... Cài đặt thẳng thì mỗi $dp[i]$ tốn một vòng for $O(N)$, tổng $O(N^2)$. Nếu nhận ra hình dạng của tập $j$, vòng for đó biến thành một truy vấn trên cấu trúc dữ liệu (deque, Fenwick, cây phân đoạn, ngăn xếp, bảng nhảy nhị phân), đưa bài xuống $O(N)$ hoặc $O(N\log N)$.

Trang này là bước tiếp theo sau khi đã nắm quy hoạch động cơ bản và các cấu trúc Fenwick, cây phân đoạn, ngăn xếp / deque đơn điệu.

Ý tưởng / Trực giác

Tách công thức thành "tập $j$" và "phép gộp"

Viết lại mọi công thức chuyển trạng thái dưới dạng

$$dp[i]=w_i\oplus {⨂}_{j\in S(i)}(dp[j]+c(j,i))$$

trong đó $⨂$ là min, max hoặc tổng, $S(i)$ là tập các $j$ được phép chuyển tới $i$, và $c(j,i)$ là chi phí chuyển. Vòng for ngây thơ duyệt hết $S(i)$. Muốn tăng tốc, cần trả lời ba câu hỏi:

1. $S(i)$ có hình dạng gì? Một đoạn chỉ số trượt dần sang phải, một đoạn chỉ số bất kỳ, một tiền tố theo giá trị, hay "mọi $j$ trong phạm vi của phần tử lớn nhất gần nhất"?
2. $c(j,i)$ tách được không? Nếu $c(j,i)=f(j)+g(i)$ thì chỉ cần lưu $dp[j]+f(j)$ vào cấu trúc tại vị trí $j$, còn $g(i)$ cộng sau. Nếu $c(j,i)$ là tích $f(j)·g(i)$ thì đó là địa bàn của DP tối ưu hóa (Convex Hull Trick). Nếu $c(j,i)$ thay đổi theo $i$ cho cả một khối $j$ (ví dụ $max(h[j+1..i])$) thì dùng ngăn xếp đơn điệu gộp các khối (mẫu 4), hoặc cây phân đoạn lười khi có thêm biên trái $j\ge l{o}_i$ (mẫu 5).
3. Phép gộp có tính chất gì? Tổng và min/max đều gộp được theo đoạn. Tổng còn trừ được, nên với tổng có thể dùng Fenwick cho truy vấn đoạn bất kỳ; min/max không trừ được nên truy vấn đoạn bất kỳ cần cây phân đoạn (hoặc Fenwick chỉ khi luôn hỏi tiền tố).

Khi đã có câu trả lời, chọn cấu trúc theo bảng:

Vì sao đúng: cấu trúc chỉ là "bộ nhớ đệm" của vòng for

Cấu trúc dữ liệu không thay đổi công thức, nó chỉ trả lời đúng câu hỏi mà vòng for trả lời, miễn là tại thời điểm truy vấn cho $i$ nó chứa chính xác các $dp[j]$ với $j\in S(i)$, không thiếu, không thừa. Mọi lỗi của kỹ thuật này đều là vi phạm câu đó, nên trước khi code hãy trả lời:

• Thứ tự tính: duyệt $i$ theo thứ tự nào để mọi $j\in S(i)$ đã có $dp[j]$? Thường là chỉ số tăng dần; với $dp[i]$ phụ thuộc các $j>i$ (ví dụ đi sang phải) thì duyệt ngược.
• Thứ tự cập nhật: $dp[i]$ được đưa vào cấu trúc sau khi tính xong, và trước khi tính các $i^{\prime }$ cần nó. Truy vấn cho $i$ không được thấy $dp[i]$ (nó chưa có, hoặc là giá trị rỗng) và không được thấy các $j$ chưa tính.
• Điều kiện thứ hai "miễn phí": khi $S(i)$ gồm hai điều kiện ($j<i$ và $a[j]<a[i]$), một điều kiện được bảo đảm bởi thứ tự duyệt (chỉ những $j$ đã duyệt mới có mặt trong cấu trúc), điều kiện còn lại được bảo đảm bởi truy vấn (tiền tố theo giá trị). Đây là mẹo trung tâm: duyệt theo một chiều, đánh chỉ số cấu trúc theo chiều kia. Có ba điều kiện thì cần thêm một tầng như CDQ.

Ví dụ chạy tay: đếm dãy con tăng bằng Fenwick

Đếm số dãy con tăng ngặt (khác rỗng) của $a=[3,1,3,2,4]$, đồng thời tính độ dài dãy con tăng dài nhất (LIS).

Gọi $cnt[i]$ là số dãy con tăng kết thúc tại $i$, $len[i]$ là độ dài LIS kết thúc tại $i$:

$$cnt[i]=1+\sum _{j<i,a[j]<a[i]}cnt[j],len[i]=1+{max}_{j<i,a[j]<a[i]}len[j].$$

Điều kiện $j<i$ lo bằng thứ tự duyệt; điều kiện $a[j]<a[i]$ thành tiền tố theo hạng: nén giá trị $\{1,2,3,4\}\to$ hạng $1.\mathrm{.4}$, rồi hỏi tổng / max trên hạng $1..r-1$ với $r$ là hạng của $a[i]$. Bảng dưới vẽ mảng theo hạng mà Fenwick đang biểu diễn (Fenwick trả về tổng tiền tố của mảng cntTree và max tiền tố của mảng lenTree), ô vừa thay đổi đánh dấu *:

hạng:            1    2    3    4
giá trị:         1    2    3    4

i=1  a=3 r=3   hỏi hạng 1..2: sum=0, max=0   -> cnt=1, len=1
     cntTree  [  0    0    1*   0 ]
     lenTree  [  0    0    1*   0 ]

i=2  a=1 r=1   hỏi hạng 1..0: rỗng           -> cnt=1, len=1
     cntTree  [  1*   0    1    0 ]
     lenTree  [  1*   0    1    0 ]

i=3  a=3 r=3   hỏi hạng 1..2: sum=1, max=1   -> cnt=2, len=2    ({3}, {1,3})
     cntTree  [  1    0    3*   0 ]          (cộng dồn: 1 + 2)
     lenTree  [  1    0    2*   0 ]          (lấy max: max(1, 2))

i=4  a=2 r=2   hỏi hạng 1..1: sum=1, max=1   -> cnt=2, len=2    ({2}, {1,2})
     cntTree  [  1    2*   3    0 ]
     lenTree  [  1    2*   2    0 ]

i=5  a=4 r=4   hỏi hạng 1..3: sum=6, max=2   -> cnt=7, len=3
     cntTree  [  1    2    3    7*]
     lenTree  [  1    2    2    3*]

Tổng số dãy con tăng = 1 + 1 + 2 + 2 + 7 = 13,  LIS = 3  (ví dụ 1, 2, 4)

Hai điểm đáng chú ý ở bước $i=3$:

• $a[3]=3$ trùng giá trị với $a[1]$. Vì hỏi hạng $1..r-1$ (không gồm $r$), $a[1]$ không được tính là phần tử đứng trước, đúng với yêu cầu tăng ngặt. Nếu đề là không giảm thì hỏi $1..r$.
• Hỏi trước, cập nhật sau. Với tăng ngặt, truy vấn chỉ tới hạng $r-1$ nên thứ tự này chưa lộ ra; nhưng với bài không giảm (hỏi tới hạng $r$), nếu đưa phần tử $i$ vào cây trước khi hỏi thì dãy kết thúc tại $i$ bị ghép với chính nó.

Kiểm tra bằng tay: $7$ dãy kết thúc tại $a[5]=4$ là $\{4\}$, $\{3,4\}$ (hai cách chọn số $3$), $\{1,4\}$, $\{1,3,4\}$, $\{2,4\}$, $\{1,2,4\}$, khớp.

Cài đặt

Mẫu 1: cửa sổ trượt trên chỉ số (deque đơn điệu)

Bài: các hòn đá $1..n$ có phí $c_i$, xuất phát ở ô $0$, đích ở ô $n+1$ (phí $0$), mỗi bước nhảy xa tối đa $k$ ô. Phí nhỏ nhất?

$$dp[i]=c_i+{min}_{i-k\le j\le i-1}dp[j].$$

Cả hai biên của cửa sổ chỉ tăng, nên deque giữ các chỉ số có $dp$ tăng dần từ đầu tới cuối: đầu deque là min của cửa sổ, phần tử nào vừa cũ hơn vừa tệ hơn một phần tử mới thì không bao giờ còn được chọn và bị bỏ.

#include <bits/stdc++.h>
using namespace std;
// Stones 1..n with cost c[i]; start at 0, finish at n+1; each jump at most k.
// dp[i] = c[i] + min(dp[j]) for i-k <= j <= i-1.
int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> c(n + 2, 0), dp(n + 2);
    for (int i = 1; i <= n; i++) cin >> c[i];
    deque<int> dq;              // indices, dp increasing from front to back
    dp[0] = 0;
    dq.push_back(0);
    for (int i = 1; i <= n + 1; i++) {
        while (dq.front() < i - k) dq.pop_front();          // drop expired j
        dp[i] = c[i] + dp[dq.front()];                      // best j in window
        while (!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back();
        dq.push_back(i);                                    // i becomes a candidate
    }
    cout << dp[n + 1] << "\n";
}

Phần lý thuyết deque đơn điệu và phiên bản ngắn của mẫu này có ở ngăn xếp và deque đơn điệu. Dạng thường gặp hơn trong đề thi là nhiều tầng: chọn đúng $x$ vị trí, mỗi $k$ vị trí liên tiếp có ít nhất một vị trí được chọn, tổng lớn nhất. Khi đó $f[c][i]=a_i+{max}_{i-k\le j<i}f[c-1][j]$: mỗi tầng $c$ chạy một deque riêng trên tầng $c-1$ (đã tính xong, cố định), tổng $O(n·x)$ thay vì $O(n·x·k)$.

#include <bits/stdc++.h>
using namespace std;
const long long NEG = LLONG_MIN / 4;
// Choose exactly x positions, every k consecutive contain one chosen; maximize sum.
// f[c][i] = a[i] + max f[c-1][j], i-k <= j <= i-1 (j = 0 is the virtual start).
int main() {
    int n, k, x;
    cin >> n >> k >> x;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<long long> prev(n + 1, NEG), cur(n + 1);
    prev[0] = 0;                                   // layer 0: only the start
    for (int c = 1; c <= x; c++) {
        deque<int> dq;                             // j of layer c-1, prev[] decreasing
        cur.assign(n + 1, NEG);
        for (int i = 1; i <= n; i++) {
            int j = i - 1;                         // j enters the window
            while (!dq.empty() && prev[dq.back()] <= prev[j]) dq.pop_back();
            dq.push_back(j);
            while (dq.front() < i - k) dq.pop_front();
            if (prev[dq.front()] > NEG) cur[i] = prev[dq.front()] + a[i];
        }
        swap(prev, cur);
    }
    long long ans = NEG;
    // last pick within the last k positions; max(1, ...) keeps the index valid when k > n
    for (int i = max(1, n - k + 1); i <= n; i++) ans = max(ans, prev[i]);
    cout << (ans <= NEG ? -1 : ans) << "\n";
}

Mẫu 2: điều kiện trên giá trị (Fenwick trên giá trị đã nén)

Đây là đoạn code của ví dụ chạy tay: một cây Fenwick tổng (đếm dãy con tăng, modulo) và một cây Fenwick max (LIS). Fenwick max dùng được vì luôn hỏi tiền tố và giá trị tại mỗi hạng chỉ tăng.

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1'000'000'007;

// Fenwick for prefix sums (mod) and prefix max, indexed 1..m.
struct FenwickSum {
    int m; vector<long long> t;
    FenwickSum(int m) : m(m), t(m + 1, 0) {}
    void add(int i, long long v) { for (; i <= m; i += i & -i) t[i] = (t[i] + v) % MOD; }
    long long sum(int i) { long long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s % MOD; }
};
struct FenwickMax {
    int m; vector<int> t;
    FenwickMax(int m) : m(m), t(m + 1, 0) {}
    void upd(int i, int v) { for (; i <= m; i += i & -i) t[i] = max(t[i], v); }
    int get(int i) { int r = 0; for (; i > 0; i -= i & -i) r = max(r, t[i]); return r; }
};

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    // Coordinate compression: rank in 1..m.
    vector<long long> vals(a.begin(), a.end());
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int m = vals.size();
    FenwickSum cntTree(m);
    FenwickMax lenTree(m);
    long long total = 0;
    int best = 0;
    for (int i = 0; i < n; i++) {
        int r = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
        // Query strictly smaller values: ranks 1..r-1. Query BEFORE update.
        long long cnt = (1 + cntTree.sum(r - 1)) % MOD;  // 1 = subsequence {a[i]} alone
        int len = 1 + lenTree.get(r - 1);
        cntTree.add(r, cnt);
        lenTree.upd(r, len);
        total = (total + cnt) % MOD;
        best = max(best, len);
    }
    cout << best << " " << total << "\n";   // LIS length, number of increasing subsequences
}

Bản Python cho phần đếm (đọc toàn bộ dữ liệu một lần cho nhanh):

import sys
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    MOD = 10**9 + 7
    vals = sorted(set(a))
    m = len(vals)
    tree = [0] * (m + 1)             # Fenwick of counts by rank
    total = 0
    for x in a:
        r = bisect_left(vals, x) + 1
        # prefix sum over ranks 1..r-1 (strictly smaller values)
        i, s = r - 1, 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        cnt = (1 + s) % MOD
        total = (total + cnt) % MOD
        i = r
        while i <= m:
            tree[i] = (tree[i] + cnt) % MOD
            i += i & -i
    print(total)

main()

So với LIS bằng lower_bound ở trang quy hoạch động, cách Fenwick dài hơn nhưng tổng quát hơn: đổi "độ dài" thành "tổng trọng số", "số cách", "độ dài kèm số cách đạt" (lưu cặp và gộp) đều chỉ là đổi phép gộp của cây.

Mẫu 3: đoạn chỉ số bất kỳ (cây phân đoạn, cập nhật điểm)

Bài: ô $i$ chỉ nhận bước nhảy dài từ $l{o}_i$ tới $h{i}_i$, tức $j\in [i-h{i}_i,i-l{o}_i]$. Các đoạn này không trượt đều (biên trái có thể lùi), nên deque không dùng được. Cây phân đoạn min trên chỉ số $j$, mỗi $dp[i]$ tính xong thì gán vào vị trí $i$.

#include <bits/stdc++.h>
using namespace std;
const long long INF = LLONG_MAX / 4;

// Iterative segment tree: point assign, range min on [l, r].
struct SegMin {
    int n; vector<long long> t;
    SegMin(int n) : n(n), t(2 * n, INF) {}
    void set(int i, long long v) {
        for (t[i += n] = v; i > 1; i >>= 1) t[i >> 1] = min(t[i], t[i ^ 1]);
    }
    long long query(int l, int r) {          // inclusive
        long long res = INF;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = min(res, t[l++]);
            if (r & 1) res = min(res, t[--r]);
        }
        return res;
    }
};

// Position i (1..n) can be reached from any j in [i - hi[i], i - lo[i]].
// dp[0] = 0; dp[i] = c[i] + min dp[j]. Print dp[n] or -1.
int main() {
    int n;
    cin >> n;
    vector<long long> c(n + 1);
    vector<int> lo(n + 1), hi(n + 1);
    for (int i = 1; i <= n; i++) cin >> c[i] >> lo[i] >> hi[i];
    SegMin seg(n + 1);
    vector<long long> dp(n + 1, INF);
    dp[0] = 0;
    seg.set(0, 0);
    for (int i = 1; i <= n; i++) {
        int L = max(0, i - hi[i]), R = min(i - 1, i - lo[i]);   // only j < i
        if (L <= R) {
            long long best = seg.query(L, R);
            if (best < INF) dp[i] = best + c[i];
        }
        seg.set(i, dp[i]);                      // update AFTER computing dp[i]
    }
    cout << (dp[n] >= INF ? -1 : dp[n]) << "\n";
}

Các ô chưa đến được giữ giá trị INF trong cây; phải kiểm tra best < INF trước khi cộng, nếu không INF + c[i] có thể tràn hoặc thành một giá trị "hợp lệ" giả.

Mẫu 4: ngăn xếp đơn điệu mang theo cực trị (chi phí là max của đoạn)

Bài: chia $h_1..h_n$ thành các nhóm liên tiếp, mỗi nhóm được thưởng $max(\text{nhóm})-C$. Tổng thưởng lớn nhất?

$$dp[i]={max}_{0\le j<i}(dp[j]+max(h[j+1..i]))-C.$$

Với $i$ cố định, $max(h[j+1..i])$ là hàm bậc thang theo $j$: các $j$ chia thành khối, mỗi khối có cùng giá trị max, và ranh giới các khối chính là ngăn xếp đơn điệu giảm của $h$ ("phần tử lớn hơn gần nhất bên trái"). Mỗi phần tử ngăn xếp lưu:

• H: giá trị max chung của khối;
• bestDp: $maxdp[j]$ trong khối;
• prefBest: $max(\text{bestDp}+H)$ của khối này và mọi khối bên dưới.

Khi thêm $h_i$, các khối có H $\le h_i$ bị gộp vào khối mới (max của chúng giờ là $h_i$). Các khối bên dưới không đổi nên prefBest của chúng vẫn đúng, và $dp[i]$ đọc ngay ở đỉnh.

#include <bits/stdc++.h>
using namespace std;
// Split h[1..n] into consecutive groups. Each group earns max(group) - C.
// dp[i] = max over 0 <= j < i of dp[j] + max(h[j+1..i]) - C.
struct Block {
    long long H;        // max(h[j+1..i]) shared by every j in this block
    long long bestDp;   // max dp[j] over j in this block
    long long prefBest; // max(bestDp + H) over this block and all blocks below it
};
int main() {
    int n;
    long long C;
    cin >> n >> C;
    vector<long long> h(n + 1), dp(n + 1);
    for (int i = 1; i <= n; i++) cin >> h[i];
    dp[0] = 0;
    vector<Block> st;                          // H strictly decreasing bottom -> top
    for (int i = 1; i <= n; i++) {
        long long bestDp = dp[i - 1];          // new block holds only j = i-1
        // Blocks with H <= h[i] now all have max h[i]: merge them into the new block.
        while (!st.empty() && st.back().H <= h[i]) {
            bestDp = max(bestDp, st.back().bestDp);
            st.pop_back();
        }
        long long below = st.empty() ? LLONG_MIN : st.back().prefBest;
        st.push_back({h[i], bestDp, max(below, bestDp + h[i])});
        dp[i] = st.back().prefBest - C;        // best over ALL j < i
    }
    cout << dp[n] << "\n";
}

Chạy tay với $h=[2,9,1,3,8,4]$, $C=5$ (ngăn xếp ghi từ đáy lên đỉnh dạng (H, bestDp, prefBest)):

Đáp án $7$, ví dụ nhóm $[2,9,1,3]$ và $[8,4]$: $(9-5)+(8-5)$. Chú ý: với bài cực tiểu tổng các max, các $h_i$ không âm và không có ràng buộc nào khác thì lấy cả dãy làm một nhóm luôn tối ưu (khi $h_i\ge 0$, tổng các max không nhỏ hơn max toàn dãy; nếu có $h_i$ âm thì điều này không còn đúng); mẫu này chỉ đáng dùng khi có yếu tố kéo ngược lại, như phí $C$ ở đây, hoặc voi16_doncay nơi ngăn xếp giữ các khoảng đổ lồng nhau và mỗi phần tử mang $minf$ từ đáy tới nó.

Mẫu 5: giữ cả hàm theo $j$ trong cây phân đoạn lười

Thêm ràng buộc biên trái vào mẫu 4 thì prefBest "từ đáy" không còn dùng được (các khối dưới cùng có thể đã ra khỏi cửa sổ). Bài xếp sách: sách theo thứ tự, cao $H_i$, rộng $W_i$; mỗi giá chứa một đoạn liên tiếp có tổng bề rộng $\le L$, chiều cao giá là sách cao nhất. Tổng chiều cao nhỏ nhất:

$$dp[i]={min}_{l{o}_i\le j<i}(dp[j]+max(H[j+1..i])),$$

với $l{o}_i$ nhỏ nhất sao cho $W_{l{o}_i+1}+\dots +W_i\le L$ (hai con trỏ).

Ý tưởng: cây phân đoạn trên chiều $j$ lưu nguyên hàm $va{l}_i(j)=dp[j]+max(H[j+1..i])$ cho $i$ hiện tại. Khi $i$ tăng:

• $j=i-1$ xuất hiện với giá trị $dp[i-1]+H_i$ (gán điểm);
• mỗi khối bị bật khỏi ngăn xếp đơn điệu có max tăng từ $H_t$ lên $H_i$: cộng đoạn $H_i-H_t$ lên đúng đoạn $j$ của khối đó;
• $dp[i]$ là min trên đoạn $[l{o}_i,i-1]$.

Đây là dạng "một chiều của trạng thái được xoay vào cây phân đoạn": thay vì tính lại $va{l}_i(j)$ cho mọi $j$, ta chỉ sửa phần thay đổi giữa $i-1$ và $i$. Mỗi sách vào và ra ngăn xếp một lần, nên tổng số phép cộng đoạn là $O(n)$.

#include <bits/stdc++.h>
using namespace std;
const long long INF = LLONG_MAX / 4;

// Lazy segment tree over j = 0..n: range add, range min.
struct LazySeg {
    int n; vector<long long> mn, lz;
    LazySeg(int n) : n(n), mn(4 * n, INF), lz(4 * n, 0) {}
    void apply(int x, long long v) { mn[x] += v; lz[x] += v; }
    void push(int x) {
        if (lz[x]) { apply(2 * x, lz[x]); apply(2 * x + 1, lz[x]); lz[x] = 0; }
    }
    void add(int x, int l, int r, int ql, int qr, long long v) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { apply(x, v); return; }
        push(x);
        int m = (l + r) / 2;
        add(2 * x, l, m, ql, qr, v); add(2 * x + 1, m + 1, r, ql, qr, v);
        mn[x] = min(mn[2 * x], mn[2 * x + 1]);
    }
    void assign(int x, int l, int r, int p, long long v) {   // point set
        if (l == r) { mn[x] = v; return; }
        push(x);
        int m = (l + r) / 2;
        if (p <= m) assign(2 * x, l, m, p, v); else assign(2 * x + 1, m + 1, r, p, v);
        mn[x] = min(mn[2 * x], mn[2 * x + 1]);
    }
    long long query(int x, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return INF;
        if (ql <= l && r <= qr) return mn[x];
        push(x);
        int m = (l + r) / 2;
        return min(query(2 * x, l, m, ql, qr), query(2 * x + 1, m + 1, r, ql, qr));
    }
};

// Books in order, heights H, widths W, shelf width L.
// dp[i] = min over lo(i) <= j < i of dp[j] + max(H[j+1..i]).
// Segment tree position j stores val[j] = dp[j] + max(H[j+1..i]) for the current i.
int main() {
    int n;
    long long L;
    cin >> n >> L;
    vector<long long> H(n + 1), W(n + 1), dp(n + 1);
    for (int i = 1; i <= n; i++) cin >> H[i] >> W[i];
    LazySeg seg(n + 1);
    vector<int> st;                 // book indices, H decreasing; st[t] owns j in [st[t-1], st[t]-1]
    int lo = 0;                     // smallest valid j
    long long width = 0;            // sum W[lo+1..i]
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        // j = i-1 enters with max(H[i..i]) = H[i]
        seg.assign(1, 0, n, i - 1, dp[i - 1] + H[i]);
        // pop books shorter than H[i]; their j-ranges now have max H[i]
        while (!st.empty() && H[st.back()] <= H[i]) {
            int t = st.back(); st.pop_back();
            int from = st.empty() ? 0 : st.back();   // j in [from, t-1] had max H[t]
            seg.add(1, 0, n, from, t - 1, H[i] - H[t]);
        }
        st.push_back(i);
        width += W[i];
        while (width > L) width -= W[++lo];         // two pointers: j >= lo
        dp[i] = seg.query(1, 0, n, lo, i - 1);
    }
    cout << dp[n] << "\n";
}

Với ví dụ $L=10$, sách $(5,7),(9,2),(8,5),(13,2),(3,8)$ chương trình in $21$: giá $\{1\}$, $\{2,3,4\}$, $\{5\}$ cao $5+13+3$.

Cùng tư tưởng "quét một chiều, giữ cả hàm theo chiều kia trong cây phân đoạn" áp dụng cho cả những bài không phải QHĐ theo nghĩa hẹp: quét đầu phải $b$, giữ $f(a)$ cho mọi đầu trái $a$, mỗi sự kiện là một phép cộng đoạn (xem quét đường thẳng).

Với QHĐ hai chiều $dp[r][c]$ mà chuyển từ hàng $r-1$ sang hàng $r$ chỉ là "cộng một hằng số lên một đoạn cột, lấy min một đoạn cột", ta cũng giữ một hàng trong cây lười và cập nhật dần thay vì tính lại cả hàng. Ví dụ cụ thể: có $m$ cột, qua mỗi bước $r=1..n$ thì mọi cột trong đoạn $[l_r,u_r]$ bị phạt thêm $w_r$, tức

$$dp[r][c]=dp[r-1][c]+w_r·[l_r\le c\le u_r],dp[0][c]=cos{t}_c,$$

và sau mỗi bước cần biết ${min}_{x_r\le c\le y_r}dp[r][c]$ (phí nhỏ nhất nếu dừng ở một cột trong đoạn cho phép). Tính lại cả hàng tốn $O(m)$ mỗi bước, tổng $O(nm)$; giữ hàng hiện tại trong cây lười của mẫu 5 thì mỗi bước là một add đoạn và một query đoạn, tổng $O(m+n\log m)$. Hàng $dp[r-1]$ không cần lưu riêng: cây luôn là hàng mới nhất.

Mẫu 6: nhảy nhiều bước theo con trỏ cố định (nhảy nhị phân)

Khi chuyển trạng thái là $f(i)=1+f(nxt[i])$ với $nxt[i]$ không phụ thuộc truy vấn, nhưng điểm dừng phụ thuộc truy vấn, thì không tính một mảng $dp$ cho từng truy vấn mà dựng bảng nhảy $up[k][i]=nxt$ lặp $2^k$ lần.

Bài: $q$ truy vấn $(L,R)$, chia $a[L..R]$ thành ít đoạn nhất sao cho mỗi đoạn gồm các phần tử đôi một khác nhau. Tham lam lấy đoạn dài nhất từ $L$ là tối ưu, và điểm bắt đầu đoạn kế $lim(L)$ không phụ thuộc $R$ (chừng nào $lim(L)\le R$). Vậy đáp án là số lần nhảy $L\to lim(L)\to \dots$ còn nằm trong $[L,R]$, cộng $1$.

#include <bits/stdc++.h>
using namespace std;
// Query (L, R): fewest segments splitting a[L..R] so that every segment has distinct values.
// Greedy takes the longest valid segment from L: next start = lim[L] (independent of R while lim[L] <= R).
// f(L, R) = 1 + f(lim[L], R); answer many queries with binary lifting on lim.
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++) cin >> a[i];
    const int LOG = 18;                               // 2^18 > 2e5
    vector<vector<int>> up(LOG, vector<int>(n + 2, n + 1));
    map<int, int> nextPos;                            // value -> next occurrence to the right
    up[0][n + 1] = n + 1;
    int lim = n + 1;                                  // lim(i) = first index j > i that repeats inside a[i..j]
    for (int i = n; i >= 1; i--) {
        auto it = nextPos.find(a[i]);
        if (it != nextPos.end()) lim = min(lim, it->second);
        nextPos[a[i]] = i;
        up[0][i] = lim;                               // greedy segment is [i, lim-1]
    }
    for (int k = 1; k < LOG; k++)
        for (int i = 1; i <= n + 1; i++) up[k][i] = up[k - 1][up[k - 1][i]];
    while (q--) {
        int L, R;
        cin >> L >> R;
        int cnt = 0, cur = L;
        for (int k = LOG - 1; k >= 0; k--)
            if (up[k][cur] <= R) { cur = up[k][cur]; cnt += 1 << k; }   // jump while still inside
        cout << cnt + 1 << "\n";                      // last segment [cur, R]
    }
}

Họ hàng của mẫu này: nếu $dp$ tính theo tầng và tầng trước đã cố định, truy vấn min/max đoạn trên tầng trước có thể dùng bảng thưa $O(1)$ mỗi truy vấn thay cho cây phân đoạn; nếu trọng số chuyển trạng thái là max trên đường đi của cây, dùng nhảy nhị phân kèm max (như voi25_ship).

Độ phức tạp

So với vòng for ngây thơ $O(n^2)$ (hoặc $O(n·q)$ cho mẫu 6), với $n=2·{10}^5$ ta đi từ $4·{10}^{10}$ xuống cỡ $4·{10}^6$ phép.

So sánh với các kỹ thuật tối ưu QHĐ khác

Hai nhóm đầu hay đi cùng nhau: Li Chao Tree là "cây phân đoạn chứa đường thẳng", dùng khi $c(j,i)=m_j·x_i$ với $x_i$ không đơn điệu; nếu tập $j$ còn bị giới hạn thêm (một đoạn chỉ số, một tiền tố giá trị) thì đặt Li Chao vào từng nút của cây phân đoạn. Còn slope trick đáng dùng khi mỗi bước làm thay đổi $dp[\text{giá trị}]$ trên toàn miền (cộng $|x-a|$, lấy min tiền tố); nếu mỗi bước chỉ một điểm thay đổi thì Fenwick hay cây phân đoạn theo giá trị (mẫu 2) là đủ.

⚠️ Lỗi thường gặp

• Cập nhật trước khi truy vấn. Đưa $dp[i]$ (hoặc giá trị rỗng của nó) vào cấu trúc rồi mới hỏi cho $i$ làm $i$ tự chuyển tới chính nó. Với tổng thì đếm sai, với max thì $dp[i]$ tự nuôi chính nó. Quy tắc: hỏi, tính, rồi mới cập nhật. Riêng mẫu 1 và 5, $j=i-1$ phải được đưa vào trước khi hỏi cho $i$ vì nó thuộc cửa sổ của $i$; đọc kỹ tập $S(i)$ có chứa $i-1$ hay không.
• Ngặt và không ngặt khi có giá trị trùng. Tăng ngặt: hỏi hạng $1..r-1$. Không giảm: hỏi $1..r$ và cập nhật sau khi hỏi. Nhầm hai trường hợp là lỗi phổ biến nhất của mẫu 2; luôn thử một test toàn số bằng nhau (với $[5,5,5]$ số dãy con tăng ngặt là $3$, không giảm là $7$).
• Quên nén giá trị hoặc nén sai. Giá trị tới ${10}^9$ không làm chỉ số Fenwick được. Sau khi sort + unique, hạng là lower_bound(...) + 1 (Fenwick đánh số từ $1$). Quên +1 thì giá trị nhỏ nhất có hạng $0$, và add(0, v) lặp vô hạn vì i += i & -i với i = 0 giữ nguyên $0$: chương trình treo (bị chấm quá thời gian), chứ không chỉ lệch một hạng; đồng thời truy vấn sum(r - 1) với r - 1 = -1 lặng lẽ trả về $0$. Ngược lại, dùng upper_bound(...) + 1 thì mọi hạng lệch lên một, giá trị lớn nhất nhận hạng $m+1$ và bị add bỏ qua, còn truy vấn $1..r-1$ lại gồm cả giá trị bằng $a[i]$, trùng đúng lỗi ngặt/không ngặt ở trên.
• Fenwick max cho truy vấn đoạn hoặc giá trị giảm. Fenwick max chỉ đúng khi luôn hỏi tiền tố và giá trị tại mỗi vị trí chỉ tăng. Cần $max$ trên $[l,r]$ bất kỳ hoặc có gán giảm thì dùng cây phân đoạn.
• Dùng deque khi biên trái có thể lùi. Deque đơn điệu đúng nhờ "phần tử đã bỏ không bao giờ quay lại cửa sổ". Nếu $L_i$ không đơn điệu (mẫu 3), một chỉ số đã bị bỏ có thể lại thuộc $S(i^{\prime })$ và bị thiếu, đáp án sai mà không có dấu hiệu gì. Kiểm tra biên trái và biên phải đều không giảm trước khi chọn deque.
• INF tràn hoặc trạng thái không đến được bị coi là $0$. Cộng chi phí vào LLONG_MAX tràn thành số âm, thành giá trị tốt nhất. Dùng INF = LLONG_MAX / 4 và kiểm tra trước khi cộng; với bài max thì khởi tạo $-\infty$ chứ không phải $0$, nếu không một chuỗi "bắt đầu giữa chừng" sẽ lọt vào.
• Modulo khi đếm. Tổng trong Fenwick phải lấy modulo ở mỗi phép cộng; khi gộp hàm sum cộng tối đa $\log n$ số nhỏ hơn MOD nên long long không tràn, nhưng nhớ lấy modulo trước khi trả về.
• Tưởng mẫu 4 là $O(n^2)$ hoặc mẫu 5 là $O(n^2\log n)$. Vòng while bật ngăn xếp lồng trong for nhưng tổng số lần bật chỉ $\le n$ (khấu hao). Ngược lại, nếu cập nhật cây bằng cách duyệt từng $j$ trong khối bị bật thì mới thật sự thành $O(n^2)$; phải dùng một phép cộng đoạn cho cả khối.
• Bảng nhảy nhị phân thiếu điểm hút. Trong mẫu 6, vị trí "ngoài mảng" ($n+1$) phải trỏ vào chính nó ở mọi tầng, và điều kiện nhảy là up[k][cur] <= R chứ không phải < R: đích của một bước là điểm bắt đầu đoạn kế tiếp, còn nằm trong $[L,R]$ nghĩa là còn cần thêm đoạn.

Biến thể / Mở rộng

• Nhiều điều kiện cùng lúc. $dp[i]$ lấy từ $j$ có $j<i$, $a[j]<a[i]$ và $b[j]<b[i]$: duyệt theo chỉ số, Fenwick theo $a$, còn $b$ thì cần một tầng chia để trị CDQ hoặc Fenwick 2 chiều.
• Chuyển trạng thái trên đồ thị có cấu trúc. Khi các cạnh $i\to j$ là "$j$ có nhãn là tiền tố của nhãn $i$" hay "$(p_i,p_j)$ thuộc danh sách cặp", cấu trúc cần dùng là trie (lưu max tại nút) hoặc chia căn theo bậc; ý tưởng vẫn là "gom $maxdp[j]$ theo nhóm để hỏi nhanh" (như voi21_bonus).
• Điều kiện là ước chung, số nguyên tố chung. Khi $j$ chuyển được tới $i$ nếu $gcd(a_j,a_i)>1$, gom theo từng thừa số nguyên tố: giữ $best[p]=maxdp[j]$ trên các $j$ đã duyệt có $p\mid a_j$; $dp[i]$ lấy max của $best[p]$ trên các thừa số nguyên tố $p$ của $a_i$ (chỉ vài số), rồi cập nhật lại các $best[p]$ đó. Chỉ khi có thêm một điều kiện giá trị (ví dụ còn cần $a_j<a_i$) mới phải thay $best[p]$ bằng một cây Fenwick riêng cho mỗi $p$. Bao hàm loại trừ (hay hàm Möbius) theo ước chỉ dùng được khi phép gộp là tổng/đếm (ví dụ đếm các $j$ có $gcd(a_j,a_i)=1$), vì cần phép trừ; với max/min thì không áp dụng được. Điều kiện hình chữ nhật trên lưới ($i^{\prime }\le i$, $j^{\prime }\le j$) thì duyệt theo hàng và Fenwick theo cột.
• Chuyển trạng thái chỉ đổi một ô. Nếu mỗi bước chỉ sửa $dp[v]$ tại một $v$ (ví dụ trạng thái là "đang đứng ở đỉnh nào"), không cần cấu trúc cho $dp$ mà cần cấu trúc để tính trọng số chuyển (max trên đường đi của cây bằng nhảy nhị phân, LCA).
• Truy vấn offline trên đoạn. Khi mỗi truy vấn là "QHĐ trên đoạn $[L,R]$", thường cố định đầu phải, quét và giữ đáp án cho mọi đầu trái trong cây phân đoạn (mẫu 5), trả lời truy vấn theo thứ tự đầu phải (xử lý truy vấn offline); nếu cần trả lời online, dùng cây phân đoạn bền vững.
• Chi phí dạng tích. $c(j,i)=f(j)·g(i)$ không tách thành tổng, cần Convex Hull Trick / Li Chao Tree.

Bài tập luyện

Luyện kỹ thuật

• Dãy Con Tăng Dài Nhất (lis) (Trung cấp) khởi động mẫu 2: viết LIS bằng Fenwick max trên giá trị đã nén thay cho lower_bound, kiểm tra test toàn số bằng nhau để chắc hỏi đúng hạng $1..r-1$.
• Dãy Con Tăng II (lis2) (Kỳ cựu) đếm số dãy con tăng ngặt modulo ${10}^9+7$: đúng code Fenwick tổng ở ví dụ chạy tay.
• Giá sách (Khó) (bookshlfgo) (Kỳ cựu) chia sách thành các giá với ràng buộc bề rộng, chi phí là sách cao nhất: mẫu 5 (ngăn xếp đơn điệu + cây phân đoạn lười + hai con trỏ cho biên trái).
• Đăng lại ảnh mèo (bản khó) (kitpics) (Kỳ cựu) chọn đúng $x$ ảnh sao cho mỗi $k$ ảnh liên tiếp có một ảnh được chọn: QHĐ nhiều tầng, mỗi tầng một deque cửa sổ trượt, $O(nx)$.
• Sereja và các dãy con (sersub) (Kỳ cựu) đếm theo các dãy con không giảm phân biệt theo giá trị: Fenwick trên giá trị (hỏi hạng $1..r$), nhưng khi gặp lại một giá trị phải thay đóng góp cũ của nó thay vì cộng thêm, để không đếm trùng.

Đề VOI

• Phân đoạn (voi05_segpar) (Nâng cao) VOI 2005: chặt nhị phân giá trị đáp án; bước kiểm tra là một QHĐ trên tiền tố mà tập $j$ hợp lệ được mô tả bằng điều kiện trên giá trị tổng tiền tố, nên gom bằng Fenwick trên giá trị đã nén (mẫu 2).
• Đường đi trên lưới (voi06_path) (Nâng cao) VOI 2006: QHĐ đếm đường đi theo ô, gom tổng theo ước bằng Fenwick theo cột, còn điều kiện "có ước chung" xử lý bằng bao hàm-loại trừ.
• Người giao hàng (voi25_ship) (Nâng cao) VOI 2025: QHĐ "đang đứng ở đảo nào" mỗi nhiệm vụ chỉ sửa một ô; phần cần cấu trúc dữ liệu là trọng số chuyển (max trên đường đi của cây), lấy bằng nhảy nhị phân kèm max. Kỹ thuật ở đây phục vụ việc tính chi phí chuyển chứ không phải truy vấn trên tập $dp[j]$.
• Đoạn số (voi22_sseq) (Nâng cao) VOI 2022: không phải QHĐ theo nghĩa hẹp, nhưng là đúng tư tưởng mẫu 5. Quét đầu phải theo thứ tự tăng, giữ giá trị của mọi đầu trái (đã nén) trong một cây phân đoạn; mỗi đoạn góp một phép cộng lên một tiền tố, cẩn thận thời điểm lấy max.
• Đốn cây (voi16_doncay) (Kỳ cựu) VOI 2016: QHĐ trên tiền tố với hai loại chuyển (cây đổ trái, cây đổ phải); với chuyển "đổ phải", các khoảng ảnh hưởng lồng nhau hoặc rời nhau, nên giữ chúng trong một ngăn xếp mà mỗi phần tử mang $minf$ từ đáy lên (mẫu 4). Cây phân đoạn min cũng đủ cho $n\le {10}^5$.
• Phần thưởng (voi21_bonus) (Kỳ cựu) VOI 2021: QHĐ từ phải sang trái, $d{p}_i=p_i+max(0,maxd{p}_j)$ trên các thẻ $j$ nối được (số $0$ ứng với việc dừng ở thẻ $i$). Hai loại cạnh cần hai cấu trúc khác nhau để gom $maxd{p}_j$: một cây cho điều kiện về nhãn, và cách xử lý theo bậc (nặng/nhẹ) cho điều kiện về cặp số.
• Bài tập đêm giáng sinh (voi24_noel) (Chuyên gia) VOI 2024: số cách phân đoạn là một QHĐ tổng trên cửa sổ; phần lớn quãng đường là các bước "chắc chắn chọn đoạn dài nhất" theo một con trỏ không phụ thuộc truy vấn, nên nhảy qua bằng bảng nhảy nhị phân (mẫu 6), chỉ tính QHĐ thật trên một đoạn ngắn cuối cùng.