cplib-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub hitonanode/cplib-cpp

:heavy_check_mark: convex_hull_trick/test/li_chao_tree.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/segment_add_get_min"
#include "../li_chao_tree.hpp"
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    std::vector<std::tuple<bool, int, int, int, long long>> qs;
    std::vector<long long> xs;

    int tp, l, r, a, p;
    long long b;

    while (N--) {
        cin >> l >> r >> a >> b;
        qs.emplace_back(false, l, r, a, b);
    }
    while (Q--) {
        cin >> tp;
        if (tp == 0) {
            cin >> l >> r >> a >> b;
            qs.emplace_back(false, l, r, a, b);
        } else {
            cin >> p;
            qs.emplace_back(true, p, 0, 0, 0);
            xs.push_back(p);
        }
    }
    li_chao_tree<long long, long long> tree;
    tree.init(xs);

    for (auto q : qs) {
        tie(tp, l, r, a, b) = q;
        if (tp == 0) tree.add_segment(l, r, a, b, 0);
        if (tp == 1) {
            auto ret = tree.get(l);
            if (ret.is_valid) {
                cout << ret.minval << '\n';
            } else {
                cout << "INFINITY\n";
            }
        }
    }
}
#line 1 "convex_hull_trick/test/li_chao_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/segment_add_get_min"
#line 2 "convex_hull_trick/li_chao_tree.hpp"
#include <algorithm>
#include <cassert>
#include <tuple>
#include <vector>

// Li-Chao tree
// init() : set x's where we will execute get(x) queries
// add_segment(l, r, a, b): update by ax + b in [l, r)
// get(x): get min
template <class T, class T_MP> struct li_chao_tree {
    int _n, _head;
    std::vector<T> xs;
    li_chao_tree() : _n(0), _head(0) {}

    struct _Line {
        T a, b;
        int line_idx;
        bool is_valid;
        T_MP eval(T x) const noexcept { return T_MP(a) * x + b; }
    };

    std::vector<_Line> lines;
    struct LCR {
        T l, c, r;
    };
    std::vector<LCR> lcr;

    void init(const std::vector<T> &xs_) {
        xs = xs_;
        std::sort(xs.begin(), xs.end());
        xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
        _n = xs.size();
        _head = 1;
        while (_head < _n) _head <<= 1;
        lines.assign(_head * 2, {0, 0, -1, false});
        lcr.resize(_head * 2);
        for (int i = 0; i < _n; ++i) lcr[_head + i] = {xs[i], xs[i], xs[i]};
        for (int i = _head - 1; i; --i) {
            int l = i * 2, r = i * 2 + 1;
            lcr[i] = {lcr[l].l, lcr[r].l, lcr[r].r};
        }
    }

    int il, ir;
    void _rec(int now, int nowl, int nowr, _Line line_add) {
        const int nowc = (nowl + nowr) / 2;

        if (nowl >= ir or nowr <= il) {
            return;
        } else if (il <= nowl and nowr <= ir) {
            if (!lines[now].is_valid) {
                lines[now] = line_add;
                return;
            }
            bool upd_l = lines[now].eval(lcr[now].l) > line_add.eval(lcr[now].l);
            bool upd_c = lines[now].eval(lcr[now].c) > line_add.eval(lcr[now].c);
            bool upd_r = lines[now].eval(lcr[now].r) > line_add.eval(lcr[now].r);
            if (upd_l and upd_c and upd_r) {
                lines[now] = line_add;
                return;
            } else if (upd_c and upd_r) {
                std::swap(lines[now], line_add);
                _rec(now * 2, nowl, nowc, line_add);
            } else if (upd_l and upd_c) {
                std::swap(lines[now], line_add);
                _rec(now * 2 + 1, nowc, nowr, line_add);
            } else if (upd_l) {
                _rec(now * 2, nowl, nowc, line_add);
            } else if (upd_r) {
                _rec(now * 2 + 1, nowc, nowr, line_add);
            } else {
                return;
            }
        } else {
            if (il < nowc) _rec(now * 2, nowl, nowc, line_add);
            if (ir > nowc) _rec(now * 2 + 1, nowc, nowr, line_add);
        }
    }

    void add_line(T a, T b, int idx = -1) {
        il = 0, ir = _n;
        if (il >= ir) return;
        _rec(1, 0, _head, _Line{a, b, idx, true});
    }
    void add_segment(T xl, T xr, T a, T b, int idx = -1) {
        il = std::lower_bound(xs.begin(), xs.end(), xl) - xs.begin();
        ir = std::lower_bound(xs.begin(), xs.end(), xr) - xs.begin();
        if (il >= ir) return;
        _rec(1, 0, _head, _Line{a, b, idx, true});
    }
    struct Ret {
        T line_a, line_b;
        int line_idx;
        bool is_valid;
        T_MP minval;
    };
    Ret _get_i(int i, T x) {
        i += _head;
        _Line ret = lines[i];
        T_MP val = ret.is_valid ? ret.eval(x) : 0;
        for (i /= 2; i; i /= 2) {
            if (!lines[i].is_valid) continue;
            T_MP tmp = lines[i].eval(x);
            if (!ret.is_valid or tmp < val) ret = lines[i], val = tmp;
        }
        return {ret.a, ret.b, ret.line_idx, ret.is_valid, val};
    }

    Ret get(T x) {
        int i = std::lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        assert(i < _n and xs[i] == x);
        return _get_i(i, x);
    }
};
#line 3 "convex_hull_trick/test/li_chao_tree.test.cpp"
#include <iostream>
#line 5 "convex_hull_trick/test/li_chao_tree.test.cpp"
#include <utility>
#line 7 "convex_hull_trick/test/li_chao_tree.test.cpp"
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    std::vector<std::tuple<bool, int, int, int, long long>> qs;
    std::vector<long long> xs;

    int tp, l, r, a, p;
    long long b;

    while (N--) {
        cin >> l >> r >> a >> b;
        qs.emplace_back(false, l, r, a, b);
    }
    while (Q--) {
        cin >> tp;
        if (tp == 0) {
            cin >> l >> r >> a >> b;
            qs.emplace_back(false, l, r, a, b);
        } else {
            cin >> p;
            qs.emplace_back(true, p, 0, 0, 0);
            xs.push_back(p);
        }
    }
    li_chao_tree<long long, long long> tree;
    tree.init(xs);

    for (auto q : qs) {
        tie(tp, l, r, a, b) = q;
        if (tp == 0) tree.add_segment(l, r, a, b, 0);
        if (tp == 1) {
            auto ret = tree.get(l);
            if (ret.is_valid) {
                cout << ret.minval << '\n';
            } else {
                cout << "INFINITY\n";
            }
        }
    }
}
Back to top page