Hướng giải của Cây Li Chao
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Hướng dẫn giải
Bài toán yêu cầu thêm đường thẳng \(y = a_i x + b_i\) và truy vấn giá trị nhỏ nhất tại \(x_j\).
Sử dụng cây Li Chao: mỗi nút quản lý một đoạn \([lo, hi]\) và lưu một đường thẳng. Khi thêm đường thẳng mới, ta so sánh tại trung điểm \(mid\), đường thẳng nào tệ hơn sẽ được đẩy xuống nút con.
Độ phức tạp: \(O((N+M) \log MAX)\), với MAX là phạm vi giá trị \(x\).
Mã nguồn C++
// Giải thuật ch cho bài toán ch-li-chao\n#include <bits/stdc++.h>
using namespace std;
struct Line {
long long a, b;
long long eval(long long x) { return a * x + b; }
};
struct LiChaoTree {
struct Node { Line line; int l, r; };
vector<Node> nodes;
long long lo, hi;
LiChaoTree(long long _lo, long long _hi) : lo(_lo), hi(_hi) {
nodes.push_back({{0, LLONG_MAX}, -1, -1});
}
void add_line(int idx, long long l, long long r, Line new_line) {
long long mid = l + (r - l) / 2;
bool left = new_line.eval(l) < nodes[idx].line.eval(l);
bool m = new_line.eval(mid) < nodes[idx].line.eval(mid);
if (m) swap(nodes[idx].line, new_line);
if (l == r) return;
if (left != m) {
if (nodes[idx].l == -1) {
nodes[idx].l = nodes.size();
nodes.push_back({{0, LLONG_MAX}, -1, -1});
}
add_line(nodes[idx].l, l, mid, new_line);
} else {
if (nodes[idx].r == -1) {
nodes[idx].r = nodes.size();
nodes.push_back({{0, LLONG_MAX}, -1, -1});
}
add_line(nodes[idx].r, mid + 1, r, new_line);
}
}
void add_line(Line line) { add_line(0, lo, hi, line); }
long long query(int idx, long long l, long long r, long long x) {
if (idx == -1) return LLONG_MAX;
long long res = nodes[idx].line.eval(x);
if (l == r) return res;
long long mid = l + (r - l) / 2;
if (x <= mid)
res = min(res, query(nodes[idx].l, l, mid, x));
else
res = min(res, query(nodes[idx].r, mid + 1, r, x));
return res;
}
long long query(long long x) { return query(0, lo, hi, x); }
};
int main() {
// Doc du lieu dau vao
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
LiChaoTree tree(-1e9, 1e9);
for (int i = 0; i < n; i++) {
// Duyet qua tung phan tu
long long a, b; cin >> a >> b;
tree.add_line({a, b});
}
vector<long long> ans(m);
for (int i = 0; i < m; i++) {
long long x; cin >> x;
ans[i] = tree.query(x);
}
for (int i = 0; i < m; i++)
cout << ans[i] << " \n"[i == m-1];
return 0;
}
Nhận xét