cp-library-cpp

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

View the Project on GitHub suisen-cp/cp-library-cpp

:heavy_check_mark: test/src/datastructure/segment_tree/persistent_lazy_segment_tree/dummy.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

#include <iostream>
#include <limits>

#include "library/datastructure/segment_tree/persistent_lazy_segment_tree.hpp"

template <typename T, T(*op)(T, T), T(*e)(), typename F, T(*mapping)(F, T)>
struct NaiveSolutionForLazySegmentTree {
    NaiveSolutionForLazySegmentTree() = default;
    NaiveSolutionForLazySegmentTree(const std::vector<T> &dat) : _n(dat.size()), _dat(dat) {}

    T get(int i) const {
        assert(0 <= i and i < _n);
        return _dat[i];
    }
    void set(int i, const T& val) {
        assert(0 <= i and i < _n);
        _dat[i] = val;
    }

    T prod_all() const {
        return prod(0, _n);
    }
    T prod(int l, int r) const {
        assert(0 <= l and l <= r and r <= _n);
        T res = e();
        for (int i = l; i < r; ++i) res = op(res, _dat[i]);
        return res;
    }

    void apply_all(const F &f) {
        apply(0, _n, f);
    }
    void apply(int l, int r, const F &f) {
        assert(0 <= l and l <= r and r <= _n);
        for (int i = l; i < r; ++i) _dat[i] = mapping(f, _dat[i]);
    }

    template <typename Pred>
    int max_right(int l, Pred &&pred) const {
        assert(0 <= l and l <= _n);
        T sum = e();
        for (int r = l; r < _n; ++r) {
            T next_sum = op(sum, _dat[r]);
            if (not pred(next_sum)) return r;
            sum = std::move(next_sum);
        }
        return _n;
    }

    template <typename Pred>
    int min_left(int r, Pred &&pred) const {
        assert(0 <= r and r <= _n);
        T sum = e();
        for (int l = r; l > 0; --l) {
            T next_sum = op(_dat[l - 1], sum);
            if (not pred(next_sum)) return l;
            sum = std::move(next_sum);
        }
        return 0;
    }
private:
    int _n;
    std::vector<T> _dat;
};

/**
 * Range Update Range Sum
 */

struct S {
    long long sum;
    int len;
    S() = default;
    S(long long sum, int len) : sum(sum), len(len) {}

    bool operator==(const S &other) const {
        return sum == other.sum and len == other.len;
    }
    bool operator!=(const S &other) const {
        return not operator==(other);
    }
};

struct F {
    static constexpr int identity = std::numeric_limits<int>::max();

    int val;
    F() : val(identity) {}
    F(int val) : val(val) {}
};

S op(S x, S y) {
    return S{ x.sum + y.sum, x.len + y.len };
}
S e() {
    return S{ 0LL, 0 };
}
S mapping(F f, S x) {
    return f.val == F::identity ? x : S{ (long long) f.val * x.len, x.len };
}
F composition(F f, F g) {
    return f.val == F::identity ? g : f;
}
F id() {
    return F{};
}

using Tree = suisen::PersistentLazySegmentTree<S, op, e, F, mapping, composition, id>;
using Naive = NaiveSolutionForLazySegmentTree<S, op, e, F, mapping>;

#include <random>
#include <algorithm>

constexpr int Q_get = 0;
constexpr int Q_set = 1;
constexpr int Q_prod = 2;
constexpr int Q_prod_all = 3;
constexpr int Q_apply = 4;
constexpr int Q_apply_all = 5;
constexpr int Q_max_right = 6;
constexpr int Q_min_left = 7;
constexpr int QueryTypeNum = 8;

void test() {
    constexpr int N = 3000, Q = 3000, MAX_VAL = 1000000000;

    std::mt19937 rng{std::random_device{}()};

    Tree::init_pool(1000000);

    std::vector<S> init(N);
    for (int i = 0; i < N; ++i) init[i] = { (long long) rng() % MAX_VAL, 1 };
    
    std::vector<Tree> ts;
    std::vector<Naive> naive_sols;

    ts.push_back(Tree{init});
    naive_sols.push_back(Naive{init});

    for (int i = 0; i < Q; ++i) {
        const int query_type = rng() % QueryTypeNum;
        const int sequence_id = rng() % ts.size();
        auto &act = ts[sequence_id];
        auto &exp = naive_sols[sequence_id];
        if (query_type == Q_get) {
            const int i = rng() % N;
            assert(act.get(i) == exp.get(i));
        } else if (query_type == Q_set) {
            const int i = rng() % N;
            const S v = { (long long) rng() % MAX_VAL, 1 };
            ts.push_back(act.set(i, v));
            naive_sols.push_back(exp);
            naive_sols.back().set(i, v);
        } else if (query_type == Q_prod) {
            const int l = rng() % (N + 1);
            const int r = l + rng() % (N - l + 1);
            assert(act.prod(l, r) == exp.prod(l, r));
        } else if (query_type == Q_prod_all) {
            assert(act.prod_all() == exp.prod_all());
        } else if (query_type == Q_apply) {
            const int l = rng() % (N + 1);
            const int r = l + rng() % (N - l + 1);
            const int f = rng() % MAX_VAL;
            ts.push_back(act.apply(l, r, f));
            naive_sols.push_back(exp);
            naive_sols.back().apply(l, r, f);
        } else if (query_type == Q_apply_all) {
            const int f = rng() % MAX_VAL;
            ts.push_back(act.apply_all(f));
            naive_sols.push_back(exp);
            naive_sols.back().apply_all(f);
        } else if (query_type == Q_max_right) {
            const int l = rng() % (N + 1);
            const int r = l + rng() % (N - l + 1);
            long long sum = std::max(0LL, exp.prod(l, r).sum + int(rng() % MAX_VAL) - MAX_VAL / 2);
            auto pred = [&](const S &x) { return x.sum <= sum; };
            assert(act.max_right(l, pred) == exp.max_right(l, pred));
        } else if (query_type == Q_min_left) {
            const int l = rng() % (N + 1);
            const int r = l + rng() % (N - l + 1);
            long long sum = std::max(0LL, exp.prod(l, r).sum + int(rng() % MAX_VAL) - MAX_VAL / 2);
            auto pred = [&](const S &x) { return x.sum <= sum; };
            assert(act.min_left(r, pred) == exp.min_left(r, pred));
        } else {
            assert(false);
        }
    }
}

int main() {
    test();
    std::cout << "Hello World" << std::endl;
    return 0;
}
#line 1 "test/src/datastructure/segment_tree/persistent_lazy_segment_tree/dummy.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

#include <iostream>
#include <limits>

#line 1 "library/datastructure/segment_tree/persistent_lazy_segment_tree.hpp"



#include <cassert>

#line 1 "library/util/object_pool.hpp"



#include <deque>
#include <vector>

namespace suisen {
    template <typename T, bool auto_extend = false>
    struct ObjectPool {
        using value_type = T;
        using value_pointer_type = T*;

        template <typename U>
        using container_type = std::conditional_t<auto_extend, std::deque<U>, std::vector<U>>;

        container_type<value_type> pool;
        container_type<value_pointer_type> stock;
        decltype(stock.begin()) it;

        ObjectPool() : ObjectPool(0) {}
        ObjectPool(int siz) : pool(siz), stock(siz) {
            clear();
        }

        int capacity() const { return pool.size(); }
        int size() const { return it - stock.begin(); }

        value_pointer_type alloc() {
            if constexpr (auto_extend) ensure();
            return *it++;
        }

        void free(value_pointer_type t) {
            *--it = t;
        }

        void clear() {
            int siz = pool.size();
            it = stock.begin();
            for (int i = 0; i < siz; i++) stock[i] = &pool[i];
        }

        void ensure() {
            if (it != stock.end()) return;
            int siz = stock.size();
            for (int i = siz; i <= siz * 2; ++i) {
                stock.push_back(&pool.emplace_back());
            }
            it = stock.begin() + siz;
        }
    };
} // namespace suisen


#line 7 "library/datastructure/segment_tree/persistent_lazy_segment_tree.hpp"

namespace suisen {
    template <typename T, T(*op)(T, T), T(*e)(), typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
    struct PersistentLazySegmentTree {
        struct Node;

        using value_type = T;
        using operator_type = F;

        using node_type = Node;
        using node_pointer_type = node_type*;

        struct Node {
            static inline ObjectPool<node_type> _pool;

            node_pointer_type _ch[2]{ nullptr, nullptr };
            value_type _dat;
            operator_type _laz;

            Node() : _dat(e()), _laz(id()) {}

            static node_pointer_type clone(node_pointer_type node) {
                return &(*_pool.alloc() = *node);
            }

            static void update(node_pointer_type node) {
                node->_dat = op(node->_ch[0]->_dat, node->_ch[1]->_dat);
            }
            template <bool do_clone = true>
            static auto push(node_pointer_type node) {
                node_pointer_type res = node;
                if constexpr (do_clone) res = clone(res);
                res->_ch[0] = apply_all(res->_ch[0], res->_laz);
                res->_ch[1] = apply_all(res->_ch[1], res->_laz);
                res->_laz = id();
                if constexpr (do_clone) {
                    return res;
                } else {
                    return;
                }
            }

            static bool is_leaf(node_pointer_type node) {
                return not node->_ch[0];
            }

            static node_pointer_type build(const std::vector<value_type>& dat) {
                auto rec = [&](auto rec, int l, int r) -> node_pointer_type {
                    node_pointer_type res = _pool.alloc();
                    if (r - l == 1) {
                        res->_dat = dat[l];
                        res->_laz = id();
                    } else {
                        int m = (l + r) >> 1;
                        res->_ch[0] = rec(rec, l, m), res->_ch[1] = rec(rec, m, r);
                        update(res);
                        res->_laz = id();
                    }
                    return res;
                };
                return rec(rec, 0, dat.size());
            }

            static value_type prod_all(node_pointer_type node) {
                return node ? node->_dat : e();
            }
            static value_type prod(node_pointer_type node, int tl, int tr, int ql, int qr, const operator_type &f = id()) {
                if (tr <= ql or qr <= tl) return e();
                if (ql <= tl and tr <= qr) return mapping(f, node->_dat);
                int tm = (tl + tr) >> 1;
                operator_type g = composition(f, node->_laz);
                return op(prod(node->_ch[0], tl, tm, ql, qr, g), prod(node->_ch[1], tm, tr, ql, qr, g));
            }

            static node_pointer_type apply_all(node_pointer_type node, const operator_type &f) {
                if (not node) return nullptr;
                node_pointer_type res = clone(node);
                res->_dat = mapping(f, res->_dat);
                res->_laz = composition(f, res->_laz);
                return res;
            }
            static node_pointer_type apply(node_pointer_type node, int tl, int tr, int ql, int qr, const operator_type &f) {
                if (tr <= ql or qr <= tl) return node;
                if (ql <= tl and tr <= qr) return apply_all(node, f);
                node_pointer_type res = push(node);
                int tm = (tl + tr) >> 1;
                res->_ch[0] = apply(res->_ch[0], tl, tm, ql, qr, f);
                res->_ch[1] = apply(res->_ch[1], tm, tr, ql, qr, f);
                update(res);
                return res;
            }

            template <typename Func>
            static auto update_leaf(node_pointer_type node, int siz, int i, Func &&f) {
                static std::vector<node_pointer_type> path;

                node_pointer_type res = clone(node);
                node_pointer_type cur = res;

                for (int l = 0, r = siz; r - l > 1;) {
                    path.push_back(cur);
                    push</*do_clone = */false>(cur);
                    int m = (l + r) >> 1;
                    if (i < m) {
                        cur = cur->_ch[0];
                        r = m;
                    } else {
                        cur = cur->_ch[1];
                        l = m;
                    }
                }
                cur->_dat = f(cur->_dat);
                while (path.size()) update(path.back()), path.pop_back();
                return res;
            }

            static value_type get(node_pointer_type node, int siz, int i) {
                operator_type f = id();
                node_pointer_type cur = node;
                for (int l = 0, r = siz; r - l > 1;) {
                    f = composition(f, cur->_laz);
                    int m = (l + r) >> 1;
                    if (i < m) {
                        cur = cur->_ch[0];
                        r = m;
                    } else {
                        cur = cur->_ch[1];
                        l = m;
                    }
                }
                return mapping(f, cur->_dat);
            }
            template <typename Func>
            static node_pointer_type apply(node_pointer_type node, int siz, int i, Func&& f) {
                return update_leaf(node, siz, i, [&](const value_type &v) { return f(v); });
            }
            static node_pointer_type set(node_pointer_type node, int siz, int i, const value_type& dat) {
                return apply(node, siz, i, [&](const value_type&) { return dat; });
            }

            template <typename Pred>
            static int max_right(node_pointer_type node, int siz, int l, Pred&& pred) {
                assert(pred(e()));
                auto rec = [&](auto rec, node_pointer_type cur, int tl, int tr, value_type& sum, const operator_type &f) -> int {
                    if (tr <= l) return tr;
                    if (l <= tl) {
                        value_type nxt_sum = op(sum, mapping(f, cur->_dat));
                        if (pred(nxt_sum)) {
                            sum = std::move(nxt_sum);
                            return tr;
                        }
                        if (tr - tl == 1) return tl;
                    }
                    int tm = (tl + tr) >> 1;
                    operator_type g = composition(f, cur->_laz);
                    int res_l = rec(rec, cur->_ch[0], tl, tm, sum, g);
                    return res_l != tm ? res_l : rec(rec, cur->_ch[1], tm, tr, sum, g);
                };
                value_type sum = e();
                return rec(rec, node, 0, siz, sum, id());
            }
            template <typename Pred>
            static int min_left(node_pointer_type node, int siz, int r, Pred&& pred) {
                assert(pred(e()));
                auto rec = [&](auto rec, node_pointer_type cur, int tl, int tr, value_type& sum, const operator_type &f) -> int {
                    if (r <= tl) return tl;
                    if (tr <= r) {
                        value_type nxt_sum = op(mapping(f, cur->_dat), sum);
                        if (pred(nxt_sum)) {
                            sum = std::move(nxt_sum);
                            return tl;
                        }
                        if (tr - tl == 1) return tr;
                    }
                    int tm = (tl + tr) >> 1;
                    operator_type g = composition(f, cur->_laz);
                    int res_r = rec(rec, cur->_ch[1], tm, tr, sum, g);
                    return res_r != tm ? res_r : rec(rec, cur->_ch[0], tl, tm, sum, g);
                };
                value_type sum = e();
                return rec(rec, node, 0, siz, sum, id());
            }

            template <typename OutputIterator>
            static void dump(node_pointer_type node, OutputIterator it) {
                if (not node) return;
                auto rec = [&](auto rec, node_pointer_type cur, const operator_type &f) -> void {
                    if (is_leaf(cur)) {
                        *it++ = mapping(f, cur->_dat);
                    } else {
                        *it++ = mapping(f, cur->_dat);
                        rec(rec, cur->_ch[0], composition(cur->_laz, f)), rec(rec, cur->_ch[1], composition(cur->_laz, f));
                    }
                };
                rec(rec, node, id());
            }
            static std::vector<value_type> dump(node_pointer_type node) {
                std::vector<value_type> res;
                dump(node, std::back_inserter(res));
                return res;
            }
        };

        PersistentLazySegmentTree() : _n(0), _root(nullptr) {}
        explicit PersistentLazySegmentTree(int n) : PersistentLazySegmentTree(std::vector<value_type>(n, e())) {}
        PersistentLazySegmentTree(const std::vector<value_type>& dat) : _n(dat.size()), _root(node_type::build(dat)) {}

        static void init_pool(int siz) {
            node_type::_pool = ObjectPool<node_type>(siz);
        }
        static void clear_pool() {
            node_type::_pool.clear();
        }

        value_type prod_all() {
            return node_type::prod_all(_root);
        }
        value_type prod(int l, int r) {
            assert(0 <= l and l <= r and r <= _n);
            return node_type::prod(_root, 0, _n, l, r);
        }
        value_type operator()(int l, int r) {
            return prod(l, r);
        }

        PersistentLazySegmentTree apply_all(const operator_type &f) {
            return PersistentLazySegmentTree(_n, node_type::apply_all(_root, f));
        }
        PersistentLazySegmentTree apply(int l, int r, const operator_type &f) {
            return PersistentLazySegmentTree(_n, node_type::apply(_root, 0, _n, l, r, f));
        }

        value_type get(int i) {
            assert(0 <= i and i < _n);
            return node_type::get(_root, _n, i);
        }
        value_type operator[](int i) {
            return get(i);
        }

        template <typename Func>
        PersistentLazySegmentTree apply(int i, Func&& f) {
            assert(0 <= i and i < _n);
            return PersistentLazySegmentTree(_n, node_type::apply(_root, _n, i, std::forward<F>(f)));
        }
        PersistentLazySegmentTree set(int i, const value_type& v) {
            assert(0 <= i and i < _n);
            return PersistentLazySegmentTree(_n, node_type::set(_root, _n, i, v));
        }

        template <typename Pred>
        int max_right(int l, Pred&& pred) {
            assert(0 <= l and l <= _n);
            return node_type::max_right(_root, _n, l, std::forward<Pred>(pred));
        }
        template <bool(*pred)(value_type)>
        static int max_right(int l) {
            return max_right(l, pred);
        }
        template <typename Pred>
        int min_left(int r, Pred&& pred) {
            assert(0 <= r and r <= _n);
            return node_type::min_left(_root, _n, r, std::forward<Pred>(pred));
        }
        template <bool(*pred)(value_type)>
        static int min_left(int r) {
            return min_left(r, pred);
        }

        template <typename OutputIterator>
        void dump(OutputIterator it) {
            node_type::dump(_root, it);
        }
        std::vector<value_type> dump() {
            return node_type::dump(_root);
        }

    private:
        int _n;
        node_pointer_type _root;
        PersistentLazySegmentTree(int n, node_pointer_type root) : _n(n), _root(root) {}
    };
}


#line 7 "test/src/datastructure/segment_tree/persistent_lazy_segment_tree/dummy.test.cpp"

template <typename T, T(*op)(T, T), T(*e)(), typename F, T(*mapping)(F, T)>
struct NaiveSolutionForLazySegmentTree {
    NaiveSolutionForLazySegmentTree() = default;
    NaiveSolutionForLazySegmentTree(const std::vector<T> &dat) : _n(dat.size()), _dat(dat) {}

    T get(int i) const {
        assert(0 <= i and i < _n);
        return _dat[i];
    }
    void set(int i, const T& val) {
        assert(0 <= i and i < _n);
        _dat[i] = val;
    }

    T prod_all() const {
        return prod(0, _n);
    }
    T prod(int l, int r) const {
        assert(0 <= l and l <= r and r <= _n);
        T res = e();
        for (int i = l; i < r; ++i) res = op(res, _dat[i]);
        return res;
    }

    void apply_all(const F &f) {
        apply(0, _n, f);
    }
    void apply(int l, int r, const F &f) {
        assert(0 <= l and l <= r and r <= _n);
        for (int i = l; i < r; ++i) _dat[i] = mapping(f, _dat[i]);
    }

    template <typename Pred>
    int max_right(int l, Pred &&pred) const {
        assert(0 <= l and l <= _n);
        T sum = e();
        for (int r = l; r < _n; ++r) {
            T next_sum = op(sum, _dat[r]);
            if (not pred(next_sum)) return r;
            sum = std::move(next_sum);
        }
        return _n;
    }

    template <typename Pred>
    int min_left(int r, Pred &&pred) const {
        assert(0 <= r and r <= _n);
        T sum = e();
        for (int l = r; l > 0; --l) {
            T next_sum = op(_dat[l - 1], sum);
            if (not pred(next_sum)) return l;
            sum = std::move(next_sum);
        }
        return 0;
    }
private:
    int _n;
    std::vector<T> _dat;
};

/**
 * Range Update Range Sum
 */

struct S {
    long long sum;
    int len;
    S() = default;
    S(long long sum, int len) : sum(sum), len(len) {}

    bool operator==(const S &other) const {
        return sum == other.sum and len == other.len;
    }
    bool operator!=(const S &other) const {
        return not operator==(other);
    }
};

struct F {
    static constexpr int identity = std::numeric_limits<int>::max();

    int val;
    F() : val(identity) {}
    F(int val) : val(val) {}
};

S op(S x, S y) {
    return S{ x.sum + y.sum, x.len + y.len };
}
S e() {
    return S{ 0LL, 0 };
}
S mapping(F f, S x) {
    return f.val == F::identity ? x : S{ (long long) f.val * x.len, x.len };
}
F composition(F f, F g) {
    return f.val == F::identity ? g : f;
}
F id() {
    return F{};
}

using Tree = suisen::PersistentLazySegmentTree<S, op, e, F, mapping, composition, id>;
using Naive = NaiveSolutionForLazySegmentTree<S, op, e, F, mapping>;

#include <random>
#include <algorithm>

constexpr int Q_get = 0;
constexpr int Q_set = 1;
constexpr int Q_prod = 2;
constexpr int Q_prod_all = 3;
constexpr int Q_apply = 4;
constexpr int Q_apply_all = 5;
constexpr int Q_max_right = 6;
constexpr int Q_min_left = 7;
constexpr int QueryTypeNum = 8;

void test() {
    constexpr int N = 3000, Q = 3000, MAX_VAL = 1000000000;

    std::mt19937 rng{std::random_device{}()};

    Tree::init_pool(1000000);

    std::vector<S> init(N);
    for (int i = 0; i < N; ++i) init[i] = { (long long) rng() % MAX_VAL, 1 };
    
    std::vector<Tree> ts;
    std::vector<Naive> naive_sols;

    ts.push_back(Tree{init});
    naive_sols.push_back(Naive{init});

    for (int i = 0; i < Q; ++i) {
        const int query_type = rng() % QueryTypeNum;
        const int sequence_id = rng() % ts.size();
        auto &act = ts[sequence_id];
        auto &exp = naive_sols[sequence_id];
        if (query_type == Q_get) {
            const int i = rng() % N;
            assert(act.get(i) == exp.get(i));
        } else if (query_type == Q_set) {
            const int i = rng() % N;
            const S v = { (long long) rng() % MAX_VAL, 1 };
            ts.push_back(act.set(i, v));
            naive_sols.push_back(exp);
            naive_sols.back().set(i, v);
        } else if (query_type == Q_prod) {
            const int l = rng() % (N + 1);
            const int r = l + rng() % (N - l + 1);
            assert(act.prod(l, r) == exp.prod(l, r));
        } else if (query_type == Q_prod_all) {
            assert(act.prod_all() == exp.prod_all());
        } else if (query_type == Q_apply) {
            const int l = rng() % (N + 1);
            const int r = l + rng() % (N - l + 1);
            const int f = rng() % MAX_VAL;
            ts.push_back(act.apply(l, r, f));
            naive_sols.push_back(exp);
            naive_sols.back().apply(l, r, f);
        } else if (query_type == Q_apply_all) {
            const int f = rng() % MAX_VAL;
            ts.push_back(act.apply_all(f));
            naive_sols.push_back(exp);
            naive_sols.back().apply_all(f);
        } else if (query_type == Q_max_right) {
            const int l = rng() % (N + 1);
            const int r = l + rng() % (N - l + 1);
            long long sum = std::max(0LL, exp.prod(l, r).sum + int(rng() % MAX_VAL) - MAX_VAL / 2);
            auto pred = [&](const S &x) { return x.sum <= sum; };
            assert(act.max_right(l, pred) == exp.max_right(l, pred));
        } else if (query_type == Q_min_left) {
            const int l = rng() % (N + 1);
            const int r = l + rng() % (N - l + 1);
            long long sum = std::max(0LL, exp.prod(l, r).sum + int(rng() % MAX_VAL) - MAX_VAL / 2);
            auto pred = [&](const S &x) { return x.sum <= sum; };
            assert(act.min_left(r, pred) == exp.min_left(r, pred));
        } else {
            assert(false);
        }
    }
}

int main() {
    test();
    std::cout << "Hello World" << std::endl;
    return 0;
}
Back to top page