test/yosupo/line_add_get_min.lct.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 01:32:22+09:00
• Problem: https://judge.yosupo.jp/problem/line_add_get_min

Depends on

• Li Chao Tree (data-structure/cht/li_chao_tree.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"

#include <bits/stdc++.h>

#include "../../data-structure/cht/li_chao_tree.hpp"
using namespace std;
using ll = long long;

struct Query {
    int t;
    ll a, b, p;
    Query(int t, ll a, ll b) : t(t), a(a), b(b) {}
    Query(int t, ll p) : t(t), p(p) {}
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<pair<ll, ll>> ab(N);
    for (int i = 0; i < N; ++i) cin >> ab[i].first >> ab[i].second;
    vector<Query> query;
    vector<ll> xs;
    for (int i = 0; i < Q; ++i) {
        int t;
        cin >> t;
        if (t == 0) {
            ll a, b;
            cin >> a >> b;
            query.emplace_back(t, a, b);
        } else {
            ll p;
            cin >> p;
            query.emplace_back(t, p);
            xs.push_back(p);
        }
    }
    LiChaoTree<ll> lct(xs);
    for (auto& p : ab) {
        lct.add_line(p.first, p.second);
    }
    for (auto& q : query) {
        if (q.t == 0) {
            lct.add_line(q.a, q.b);
        } else {
            cout << lct.get(q.p) << "\n";
        }
    }
}

#line 1 "test/yosupo/line_add_get_min.lct.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"

#include <bits/stdc++.h>

#line 3 "data-structure/cht/li_chao_tree.hpp"
#include <bit>
#line 7 "data-structure/cht/li_chao_tree.hpp"

template <typename T>
class LiChaoTree {
   public:
    LiChaoTree() = default;
    explicit LiChaoTree(const std::vector<T>& vs) : xs(vs) {
        std::ranges::sort(xs);
        xs.erase(std::ranges::unique(xs).begin(), xs.end());
        size = std::bit_ceil(xs.size());
        node.resize(2 * size, {0, INF});
        while ((int)xs.size() <= size) xs.push_back(xs.back() + 1);
    }

    void add_line(T a, T b) { update({a, b}, 1, 0, size); }

    void add_segment(T a, T b, T xl, T xr) {
        int l = std::ranges::lower_bound(xs, xl) - xs.begin();
        int r = std::ranges::lower_bound(xs, xr) - xs.begin();

        Line line(a, b);
        int len = 1;
        int l0 = l, r0 = r;
        for (l += size, r += size; l < r; l >>= 1, r >>= 1, len <<= 1) {
            if (l & 1) {
                update(line, l++, l0, l0 + len);
                ++l;
                l0 += len;
            }
            if (r & 1) {
                --r;
                r0 -= len;
                update(line, r, r0, r0 + len);
            }
        }
    }

    T get(T x) const {
        int k = std::ranges::lower_bound(xs, x) - xs.begin();
        k += size;
        T res = node[k](x);
        while (k >>= 1) res = std::min(res, node[k](x));
        return res;
    }

   private:
    struct Line {
        T a, b;
        Line(T a, T b) : a(a), b(b) {}
        T operator()(T x) const { return a * x + b; }
    };

    static constexpr T INF = std::numeric_limits<T>::max();

    int size;
    std::vector<T> xs;
    std::vector<Line> node;

    void update(Line line, int k, int l, int r) {
        while (true) {
            int m = std::midpoint(l, r);
            bool left = line(xs[l]) < node[k](xs[l]);
            bool mid = line(xs[m]) < node[k](xs[m]);
            bool right = line(xs[r]) < node[k](xs[r]);

            if (!left && !right) break;
            if (left && right) {
                node[k] = line;
                break;
            }
            if (mid) std::swap(node[k], line);
            if (r - l == 1) break;
            if (left != mid) {
                k = 2 * k;
                r = m;
            } else {
                k = 2 * k + 1;
                l = m;
            }
        }
    }
};
#line 6 "test/yosupo/line_add_get_min.lct.test.cpp"
using namespace std;
using ll = long long;

struct Query {
    int t;
    ll a, b, p;
    Query(int t, ll a, ll b) : t(t), a(a), b(b) {}
    Query(int t, ll p) : t(t), p(p) {}
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<pair<ll, ll>> ab(N);
    for (int i = 0; i < N; ++i) cin >> ab[i].first >> ab[i].second;
    vector<Query> query;
    vector<ll> xs;
    for (int i = 0; i < Q; ++i) {
        int t;
        cin >> t;
        if (t == 0) {
            ll a, b;
            cin >> a >> b;
            query.emplace_back(t, a, b);
        } else {
            ll p;
            cin >> p;
            query.emplace_back(t, p);
            xs.push_back(p);
        }
    }
    LiChaoTree<ll> lct(xs);
    for (auto& p : ab) {
        lct.add_line(p.first, p.second);
    }
    for (auto& q : query) {
        if (q.t == 0) {
            lct.add_line(q.a, q.b);
        } else {
            cout << lct.get(q.p) << "\n";
        }
    }
}

Back to top page