Hướng giải của Doan thang - Them xoa doan

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 la mo rong cua Li Chao Tree co ban: moi duong thang chi co hieu luc tren mot doan \([L, R]\).

Y tuong
  • Xay dung cay phan doan tren mien gia tri cua \(None\) nen toa do.
  • Ham them duong thang duoc chinh sua de hoat dong nhu mot update doan:
    • Duyet cay phan doan, tai nut phu hoan toan boi \([L, R]\), thuc hien chen Li Chao chuan.
    • Tai nut bi phan phu, de quy xuoong ca hai con.
  • Truy van giong nhu Li Chao chuan: di tu goc den la, lay min tai moi nut.
Do phuc tap
  • Them doan thang: \(O(\log^2 M)\).
  • Truy van: \(O(\log M)\).
  • Voi \(M \le Q\) la so gia tri \(x\) phan biet.

Ma nguon C++

// Giải thuật lc cho bài toán lc-range\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 LiChaoRange {
    vector<ll> xs;
    vector<Line> tree;
    int n;

    LiChaoRange(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_full(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_full(nw, node * 2, l, m);
        else add_full(nw, node * 2 + 1, m + 1, r);
    }

    void add(Line nw, int node, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return;
        if (ql <= l && r <= qr) { add_full(nw, node, l, r); return; }
        int m = (l + r) / 2;
        add(nw, node * 2, l, m, ql, qr);
        add(nw, node * 2 + 1, m + 1, r, ql, qr);
    }

    void add(ll a, ll b, ll L, ll R) {
        int l = lower_bound(xs.begin(), xs.end(), L) - xs.begin();
        int r = upper_bound(xs.begin(), xs.end(), R) - xs.begin() - 1;
        if (l <= r) add({a, b}, 1, 0, n - 1, l, r);
    }

    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;
    struct Op { int t; ll a, b, L, R, x; };
    vector<Op> ops(Q);
    vector<ll> qx;
    for (int i = 0; i < Q; i++) {
        int t; cin >> t;
        if (t == 1) {
            ll L, R, a, b; cin >> L >> R >> a >> b;
            ops[i] = {t, a, b, L, R, 0};
            qx.push_back(L); qx.push_back(R);
        } else {
            ll x; cin >> x;
            ops[i] = {t, 0, 0, 0, 0, x};
            qx.push_back(x);
        }
    }
    if (qx.empty()) return 0;
    LiChaoRange lichao(qx);
    for (auto &op : ops) {
        if (op.t == 1) lichao.add(op.a, op.b, op.L, op.R);
        else cout << lichao.query(op.x) << "\n";
    }
    return 0;
}

Nhận xét

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