Fu_L's Library

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

View the Project on GitHub Fu-L/cp-library

:heavy_check_mark: verify/unit_test/data_structure/dynamic_li_chao_tree.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../../src/template/template.hpp"
#include "../../../src/random/permuted_congruential_generator.hpp"
#include "../../../src/data_structure/dynamic_li_chao_tree.hpp"
void test_empty_segment() {
    DynamicLiChaoTree<ll, -10, 10> cht;
    cht.add_segment(0, 0, -100, -100);
    rep(x, -10, 11) assert(cht(x) == numeric_limits<ll>::max());
}
void test_random_segments() {
    constexpr int low = -20, high = 20;
    DynamicLiChaoTree<ll, low, high> cht;
    vector<tuple<ll, ll, ll, ll>> segments;
    rep(_, 0, 200) {
        int l = rng(low, high);
        int r = rng(l, high + 1);
        int a = rng(-20, 20);
        int b = rng(-100, 100);
        cht.add_segment(l, r, a, b);
        segments.emplace_back(l, r, a, b);
        rep(x, low, high + 1) {
            ll expected = numeric_limits<ll>::max();
            for(const auto& [sl, sr, sa, sb] : segments) {
                if(sl <= x and x < sr) expected = min(expected, sa * x + sb);
            }
            assert(cht(x) == expected);
        }
    }
}
int main() {
    test_empty_segment();
    rep(_, 0, 50) test_random_segments();
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}
#line 1 "verify/unit_test/data_structure/dynamic_li_chao_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
#line 4 "src/template/template.hpp"
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/random/permuted_congruential_generator.hpp"
struct PermutedCongruentialGenerator {
    template <typename T>
        requires(is_integral_v<T> and sizeof(T) == 4) or (is_floating_point_v<T> and sizeof(T) == 8)
    inline T operator()(const T l, const T r) {
        assert(l <= r);
        if constexpr(is_integral_v<T>) {
            const unsigned int x = next32();
            if constexpr(is_signed_v<T>) {
                const uint64_t range = uint64_t(int64_t(r) - int64_t(l)) + 1;
                const uint64_t offset = range == (uint64_t(1) << 32) ? x : x % range;
                return T(int64_t(l) + int64_t(offset));
            } else {
                const uint64_t range = uint64_t(r) - uint64_t(l) + 1;
                const uint64_t offset = range == (uint64_t(1) << 32) ? x : x % range;
                return T(l + T(offset));
            }
        } else {
            static constexpr unsigned long long denom = 1ull << 53;
            const unsigned long long x = next64() >> 11;
            const double u = static_cast<double>(x) / denom;
            return l + (r - l) * u;
        }
    }

   private:
    static constexpr unsigned long long MULT = 6364136223846793005;
    static inline unsigned long long state = chrono::steady_clock::now().time_since_epoch().count();
    inline unsigned int next32() {
        unsigned long long x = state;
        state *= MULT;
        const unsigned int count = x >> 61;
        x ^= x >> 22;
        return static_cast<unsigned int>(x >> (22 + count));
    }
    inline unsigned long long next64() {
        return (static_cast<unsigned long long>(next32()) << 32) | next32();
    }
} rng;
#line 3 "src/data_structure/dynamic_li_chao_tree.hpp"
template <typename T, T x_low, T x_high>
struct DynamicLiChaoTree {
    DynamicLiChaoTree()
        : root{nullptr} {}
    void add_line(const T& a, const T& b) {
        Line x(a, b);
        root = add_line(root, x, x_low, x_high, x.get(x_low), x.get(x_high));
    }
    void add_segment(const T& l, const T& r, const T& a, const T& b) {
        assert(l <= r);
        if(l == r) return;
        Line x(a, b);
        root = add_segment(root, x, l, r - 1, x_low, x_high, x.get(x_low), x.get(x_high));
    }
    T operator()(const T& x) const {
        assert(x_low <= x and x <= x_high);
        return query(root, x_low, x_high, x);
    }

   private:
    struct Line {
        T a, b;
        Line(const T& a, const T& b)
            : a(a), b(b) {}
        inline T get(const T& x) const {
            return a * x + b;
        }
    };
    struct Node {
        Line x;
        Node *l, *r;
        Node(const Line& x)
            : x{x}, l{nullptr}, r{nullptr} {}
    };
    const T id = numeric_limits<T>::max();
    Node* root;
    Node* add_line(Node* t, Line& x, const T& l, const T& r, const T& x_l, const T& x_r) {
        if(!t) return new Node(x);
        T t_l = t->x.get(l), t_r = t->x.get(r);
        if(t_l <= x_l and t_r <= x_r) {
            return t;
        } else if(t_l >= x_l and t_r >= x_r) {
            t->x = x;
            return t;
        } else {
            T m = (l + r) / 2;
            if(m == r) --m;
            T t_m = t->x.get(m), x_m = x.get(m);
            if(t_m > x_m) {
                swap(t->x, x);
                if(x_l >= t_l) t->l = add_line(t->l, x, l, m, t_l, t_m);
                else t->r = add_line(t->r, x, m + 1, r, t_m + x.a, t_r);
            } else {
                if(t_l >= x_l) t->l = add_line(t->l, x, l, m, x_l, x_m);
                else t->r = add_line(t->r, x, m + 1, r, x_m + x.a, x_r);
            }
            return t;
        }
    }
    Node* add_segment(Node* t, Line& x, const T& a, const T& b, const T& l, const T& r, const T& x_l, const T& x_r) {
        if(r < a or b < l) return t;
        if(a <= l and r <= b) {
            Line y{x};
            return add_line(t, y, l, r, x_l, x_r);
        }
        if(t) {
            T t_l = t->x.get(l), t_r = t->x.get(r);
            if(t_l <= x_l and t_r <= x_r) return t;
        } else {
            t = new Node(Line(0, id));
        }
        T m = (l + r) / 2;
        if(m == r) --m;
        T x_m = x.get(m);
        t->l = add_segment(t->l, x, a, b, l, m, x_l, x_m);
        t->r = add_segment(t->r, x, a, b, m + 1, r, x_m + x.a, x_r);
        return t;
    }
    T query(const Node* t, const T& l, const T& r, const T& x) const {
        if(!t) return id;
        if(l == r) return t->x.get(x);
        T m = (l + r) / 2;
        if(m == r) --m;
        if(x <= m) return min(t->x.get(x), query(t->l, l, m, x));
        else return min(t->x.get(x), query(t->r, m + 1, r, x));
    }
};
#line 5 "verify/unit_test/data_structure/dynamic_li_chao_tree.test.cpp"
void test_empty_segment() {
    DynamicLiChaoTree<ll, -10, 10> cht;
    cht.add_segment(0, 0, -100, -100);
    rep(x, -10, 11) assert(cht(x) == numeric_limits<ll>::max());
}
void test_random_segments() {
    constexpr int low = -20, high = 20;
    DynamicLiChaoTree<ll, low, high> cht;
    vector<tuple<ll, ll, ll, ll>> segments;
    rep(_, 0, 200) {
        int l = rng(low, high);
        int r = rng(l, high + 1);
        int a = rng(-20, 20);
        int b = rng(-100, 100);
        cht.add_segment(l, r, a, b);
        segments.emplace_back(l, r, a, b);
        rep(x, low, high + 1) {
            ll expected = numeric_limits<ll>::max();
            for(const auto& [sl, sr, sa, sb] : segments) {
                if(sl <= x and x < sr) expected = min(expected, sa * x + sb);
            }
            assert(cht(x) == expected);
        }
    }
}
int main() {
    test_empty_segment();
    rep(_, 0, 50) test_random_segments();
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}
Back to top page