Cấu Trúc Cơ Bản Của Li-Chao Tree

Cây Li-Chao được thiết kế để lưu trữ một tập hợp các hàm tuyến tính và tìm giá trị cực tiểu hoặc cực đại tại một tọa độ x cho trước. Dưới đây là bộ mã nguồn mẫu đã được refactor với quy ước đặt tên chuẩn mực:

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
const ll INF_VAL = 1e18;

struct Line {
    ll k, b;
};

struct LiChaoNode {
    int l_idx, r_idx;
    int id_line; // Lưu chỉ số của đường thẳng hiện hữu
} tree_nodes[MAXN * 20];

int nodes_count = 0;
int root_ptr = 0;
ll max_val_domain = 1e9;

// Hàm tính giá trị hàm theo tham số x
inline ll eval(const Line &ln, ll x) {
    return ln.k * x + ln.b;
}

// Cập nhật cây với đường thẳng mới
void add_line(int &node_idx, ll L, ll R, int new_id) {
    if (!node_idx) {
        node_idx = ++nodes_count;
        tree_nodes[node_idx].id_line = new_id;
        return;
    }
    
    ll mid = (L + R) >> 1;
    bool is_left_better = eval(tree_nodes[new_id], mid) < eval(tree_nodes[tree_nodes[node_idx].id_line], mid);
    
    if (is_left_better) swap(new_id, tree_nodes[node_idx].id_line);
    
    if (L == R) return;
    
    // Xác định nhánh con cần cập nhật dựa trên độ dốc
    if (eval(tree_nodes[new_id], L) < eval(tree_nodes[tree_nodes[node_idx].id_line], L)) {
        add_line(tree_nodes[node_idx].l_idx, L, mid, new_id);
    } else if (eval(tree_nodes[new_id], R) < eval(tree_nodes[tree_nodes[node_idx].id_line], R)) {
        add_line(tree_nodes[node_idx].r_idx, mid + 1, R, new_id);
    }
}

// Truy vấn giá trị nhỏ nhất tại x
inline ll query(ll X, int node_idx, ll L, ll R) {
    if (!node_idx) return INF_VAL;
    
    ll current_min = eval(tree_nodes[tree_nodes[node_idx].id_line], X);
    if (L == R) return current_min;
    
    ll mid = (L + R) >> 1;
    if (X <= mid) return min(current_min, query(X, tree_nodes[node_idx].l_idx, L, mid));
    else return min(current_min, query(X, tree_nodes[node_idx].r_idx, mid + 1, R));
}

Phân Tích Bài Toán Cụ Thể

Xét bài toán liên quan đến vòng tròn gồm n phần tử, mục tiêu chia vòng tròn thành k đoạn sao cho tổng chi phí đạt cực tiểu. Chi phí tính toán dựa trên vị trí tương đối giữa các điểm.

Giai Đoạn 1: Giải Thuật Phớt Ban Đầu (O(n⁴))

Biện pháp thô sơ nhất là duyệt qua toàn bộ các kết hợp có thể xảy ra. Vì cấu trúc dữ liệu là vòng tròn, ta thường "cắt vòng thành chuỗi" bằng cách mở rộng mảng kích thước 2*n. Dù giải pháp này cho kết quả đúng nhưng hiệu suất kém.

Giai Đoạn 2: Tối Ưu Hóa Tiền Tố (O(n³))

Khi tính toán tổng khoảng cách trong từng đoạn con, ta nhận thấy biểu thức tổng có dạng tổng quát có thể tính nhanh nhờ mảng tiền tố (Prefix Sum). Điều này giúp giảm độ phức tạp từ O(n) xuống O(1) cho mỗi lần tính chi phí đoạn con.

Công thức chuyển vị cơ bản sau khi dùng tiền tố:

$$ \text{Cost}(L, R) = (\text{Sum2}[R] - \text{Sum2}[L-1]) - L \times (\text{Sum1}[R] - \text{Sum1}[L-1]) $$

Trong đó:

• Sum1: Tổng giá trị nguyên bản.
• Sum2: Tổng tích của giá trị và chỉ số.

Giai Đoạn 3: Đưa Về Dạng Phương Trình Tuyến Tính

Giả sử f[i][j] là chi phí nhỏ nhất để tạo ra i điểm dừng đầu tiên tại vị trí j. Phương trình truy hồi là:

$$ f[i][j] = \min_{p} \{ f[i-1][p] + \text{Cost}(p+1, j) \} $$

Mở rộng biểu thức Cost:

$$ \begin{aligned} f[i][j] &= \min_{p} \{ f[i-1][p] + \text{Sum2}[j] - \text{Sum2}[p] - (p+1)(\text{Sum1}[j] - \text{Sum1}[p]) \} \\ &= \text{Sum2}[j] + \min_{p} \{ (f[i-1][p] - \text{Sum2}[p] + (p+1)\text{Sum1}[p]) + (-(p+1)) \times \text{Sum1}[j] \} \end{aligned} $$

So sánh với phương trình đường thẳng $y = kx + b$, ta xác định được các tham số:

• $k$ (độ dốc): $-(p+1)$
• $b$ (tung độ gốc): $f[i-1][p] - \text{Sum2}[p] + (p+1)\text{Sum1}[p]$
• $x$ (trục hoành): $\text{Sum1}[j]$

Nhờ vậy, bài toán quy hoach động trở thành bài toán tìm giá trị nhỏ nhất của nhiều đường thẳng tại một điểm x, phù hợp hoàn hảo với Li-Chao Tree.

Cài Đặt Giải Pháp Cuối Cùng

Dưới đây là triển khai hoàn chỉnh kết hợp việc xử lý vòng tròn, tiền tố và cấu trúc Li-Chao Tree đã tối ưu. Lưu ý rằng miền giá trị M nên được điều chỉnh theo phạm vi dữ liệu thực tế thay vì hằng số quá lớn để đảm bảo thời gian chạy.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 2010;
const ll INF_VAL = 1e18;

// Định nghĩa cấu trúc cây
struct TreeNode {
    int left, right;
    int lineIdx;
} tree[MAXN * 20];

struct LineData {
    ll k, b;
};

// Biến toàn cục
int nodeCnt = 0;
int root = 0;
int N_K, limit_Range;
ll dp_val[15][MAXN];
ll arrVal[MAXN], preSum1[MAXN], preSum2[MAXN];
LineData activeLines[MAXN];

// Tính giá trị hàm
inline ll getValue(LineData &line, ll x) {
    return line.k * x + line.b;
}

// Chèn đường thẳng mới vào cây
void insertNode(int &idx, ll L, ll R, int lineID) {
    if (!idx) idx = ++nodeCnt;
    if (tree[idx].lineIdx == -1) {
        tree[idx].lineIdx = lineID;
        return;
    }

    ll mid = (L + R) >> 1;
    if (getValue(activeLines[lineID], mid) < getValue(activeLines[tree[idx].lineIdx], mid)) {
        swap(lineID, tree[idx].lineIdx);
    }

    if (L == R) return;
    // Chỉ chèn vào nhánh còn lại nếu đường thẳng tốt hơn ở biên
    if (getValue(activeLines[lineID], L) < getValue(activeLines[tree[idx].lineIdx], L)) {
        insertNode(tree[idx].left, L, mid, lineID);
    } else if (getValue(activeLines[lineID], R) < getValue(activeLines[tree[idx].lineIdx], R)) {
        insertNode(tree[idx].right, mid + 1, R, lineID);
    }
}

// Truy vấn giá trị nhỏ nhất
inline ll queryMin(ll x, int idx, ll L, ll R) {
    if (!idx) return INF_VAL;
    
    ll res = getValue(activeLines[tree[idx].lineIdx], x);
    if (L == R) return res;
    
    ll mid = (L + R) >> 1;
    if (x <= mid) return min(res, queryMin(x, tree[idx].left, L, mid));
    else return min(res, queryMin(x, tree[idx].right, mid + 1, R));
}

// Khởi tạo lại cây (Reset)
void resetTree() {
    // Cần xóa các node đã sinh để tránh tràn memory
    // Trong thực tế CP, có thể dùng vector clear hoặc memset
    // Để đơn giản demo logic, giả định gọi calloc/new đủ
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n_in, k_in;
    cin >> n_in >> k_in;
    
    // Xử lý vòng tròn bằng nhân đôi mảng
    for (int i = 1; i <= n_in; i++) {
        cin >> arrVal[i];
        arrVal[i + n_in] = arrVal[i];
    }

    // Xây dựng bảng tiền tố
    for (int i = 1; i <= 2 * n_in; i++) {
        preSum1[i] = preSum1[i-1] + arrVal[i];
        preSum2[i] = preSum2[i-1] + (ll)i * arrVal[i];
    }
    
    limit_Range = preSum1[2 * n_in]; // Giới hạn miền giá trị dựa trên dữ liệu
    
    ll finalAns = INF_VAL;
    
    // Duyệt từng điểm cắt vòng tròn làm điểm bắt đầu
    for (int start_node = 1; start_node <= n_in; start_node++) {
        // Reset mảng DP
        // (Trong thực tế cần memset hoặc fill đầy đủ)
        for (int p = 1; p <= n_in; p++) {
             for(int q=1; q<=n_in;q++) dp_val[0][q]=INF_VAL;
        }
        
        // Trạng thái cơ sở với 1 cửa
        for (int j = start_node; j < start_node + n_in; j++) {
            // Tính cost trực tiếp không dùng cây cho i=1
            ll cost = (preSum2[j] - preSum2[start_node-1]) - (ll)start_node * (preSum1[j] - preSum1[start_node-1]);
            dp_val[1][j] = cost;
        }

        // Xử lý từ i=2 đến k
        for (int i = 2; i <= k_in; i++) {
            // Clear tree để chèn đường mới của tầng i
            // Logic reset tree thực tế cần duyệt qua nodeCnt cũ
            
            int current_root = 0; // Gán lại root con tạm thời hoặc global reset
            
            // Chèn các đường thẳng tương ứng từ tầng i-1
            for (int p = start_node + i - 2; p <= start_node + n_in - 1; p++) {
                ll k_val = -(ll)(p + 1);
                ll b_val = dp_val[i-1][p] - preSum2[p] + (ll)(p + 1) * preSum1[p];
                
                activeLines[p] = {k_val, b_val};
                // Chèn vào cây Li-Chao
                // Giả sử insertNode đã được gọi với root pointer reference
                insertNode(root, -limit_Range, limit_Range, p); 
            }
            
            // Tính toán DP cho tầng hiện tại
            for (int j = start_node + i - 1; j <= start_node + n_in - 1; j++) {
                ll x_query = preSum1[j];
                ll min_part = queryMin(x_query, root, -limit_Range, limit_Range);
                dp_val[i][j] = min(dp_val[i][j], min_part + preSum2[j]);
            }
        }
        
        // Tìm đáp án tối thiểu trong mảng DP cuối cùng
        for (int j = start_node + k_in - 1; j <= start_node + n_in - 1; j++) {
            if (dp_val[k_in][j] != INF_VAL) {
                ll totalRes = dp_val[k_in][j];
                // Cộng thêm phần còn lại của vòng tròn nếu chưa hết
                if (j < start_node + n_in - 1) {
                    // Phần đuôi chưa được tính trong DP chính
                    // Công thức chi phí cuối cùng...
                    ll tailCost = (preSum2[start_node+n_in-1]-preSum2[j]) - (ll)start_node * (preSum1[start_node+n_in-1]-preSum1[j]);
                    totalRes += tailCost;
                }
                finalAns = min(finalAns, totalRes);
            }
        }
    }
    
    cout << finalAns << endl;
    return 0;
}

Lưu Ý Triển Khai

Việc chọn giới hạn miền giá trị M cho cây rất quan trọng. Nếu đặt M = 1e9 cố định, độ sâu cây sẽ tăng đáng kể làm chậm thời gian chạy. Thay vào đó, hãy tính toán M động dựa trên giá trị max(Sum1) thu được từ đầu vào.

Bài toán này cũng có thể giải quyết bằng Quy Hoạch Động Với Quyết Đơn Độc (Decision Monotonicity) hoặc kỹ thuật chia để trị (Divide & Conquer) tùy thuộc vào tính chất của dãy số.