Hướng giải của Duong thang - Li Chao Tree co ban

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.

Tác giả: kienadmin

Huong dan giai

Bai toan yeu cau quan ly tap hop cac duong thang va truy van gia tri nho nhat tai mot hoanh do. Day chinh la bai toan kinh dien cua Li Chao Tree.

Y tuong
  • Su dung cay phan doan (Segment Tree) tren mien gia tri cua \(x\) sau khi nen toa do.
  • Moi nut cua cay luu mot duong thang. Khi them duong thang moi, ta so sanh gia tri cua duong thang hien tai va duong thang moi tai diem giua cua doan, giu lai duong thang tot hon, day duong thang con lai xuong cay con.
  • Truy van: di tu goc den la, tinh gia tri cua duong thang tai moi nut va lay min.
Do phuc tap
  • Them duong thang: \(O(\log M)\).
  • Truy van: \(O(\log M)\).
  • Voi \(M\) la so gia tri \(x\) phan biet trong truy van, \(M \le Q\).

Ma nguon C++

// Giải thuật lc cho bài toán lc-basic\n#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 4e18;

struct Line {
    ll m, c;
    ll eval(ll x) const { return m * x + c; }
};

struct LiChao {
    vector<ll> xs;
    vector<Line> tree;
    int n;

    LiChao(vector<ll> qx) : xs(qx) {
    sort(xs.begin(), xs.end());
    // Sap xep mang
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        n = xs.size();
        tree.assign(4 * n, {0, INF});
    }

    void add(Line nw, int node, int l, int r) {
        int m = (l + r) / 2;
        Line &cur = tree[node];
        bool mb = nw.eval(xs[m]) < cur.eval(xs[m]);
        if (mb) swap(cur, nw);
        if (l == r) return;
        bool lb = nw.eval(xs[l]) < cur.eval(xs[l]);
        if (lb != mb) add(nw, node * 2, l, m);
        else add(nw, node * 2 + 1, m + 1, r);
    }

    void add(ll m, ll c) { add({m, c}, 1, 0, n - 1); }

    ll query(int idx, int node, int l, int r) {
        ll res = tree[node].eval(xs[idx]);
        if (l == r) return res;
        int m = (l + r) / 2;
        if (idx <= m) return min(res, query(idx, node * 2, l, m));
        else return min(res, query(idx, node * 2 + 1, m + 1, r));
    }

    ll query(ll x) {
        int idx = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        return query(idx, 1, 0, n - 1);
    }
};

int main() {
    // Doc du lieu dau vao
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int Q; cin >> Q;
    vector<array<ll, 3>> ops(Q);
    vector<ll> qx;
    for (int i = 0; i < Q; i++) {
        int t; cin >> t;
        if (t == 1) {
            ll a, b; cin >> a >> b;
            ops[i] = {1, a, b};
        } else {
            ll x; cin >> x;
            ops[i] = {2, x, 0};
            qx.push_back(x);
        }
    }
    if (qx.empty()) return 0;
    LiChao lichao(qx);
    for (auto &op : ops) {
        if (op[0] == 1) lichao.add(op[1], op[2]);
        else cout << lichao.query(op[1]) << "\n";
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.