library

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

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/persistent_segtree.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

#include "algebra/monoid_add.hpp"
#include "algebra/monoid_min.hpp"
#include "datastructure/persistent_segtree.hpp"
template <class M, class Naive>
void stress(std::mt19937_64& rng, const Naive& naive) {
    using S = typename M::S;
    for (int iter = 0; iter < 200; iter++) {
        int n = 1 + rng() % 20;
        std::vector<S> init(n);
        for (auto& x : init) x = S(rng() % 100);
        persistent_segtree<M> seg(init);
        std::vector<std::vector<S>> versions{init};
        std::vector<int> roots{0};
        assert(seg.size() == n);
        for (int t = 0; t < 60; t++) {
            int k = rng() % roots.size();
            int p = rng() % n;
            S x = S(rng() % 100);
            roots.push_back(seg.set(roots[k], p, x));
            std::vector<S> v = versions[k];
            v[p] = x;
            versions.push_back(v);
            int c = rng() % roots.size();
            for (int i = 0; i < n; i++) assert(seg.get(roots[c], i) == versions[c][i]);
            for (int l = 0; l <= n; l++) {
                for (int r = l; r <= n; r++) {
                    S expect = M::e();
                    for (int i = l; i < r; i++) expect = naive(expect, versions[c][i]);
                    assert(seg.prod(roots[c], l, r) == expect);
                }
            }
            assert(seg.all_prod(roots[c]) == seg.prod(roots[c], 0, n));
        }
    }
}
int main() {
    std::mt19937_64 rng(20261027);
    stress<monoid_add<long long>>(rng, [](long long a, long long b) { return a + b; });
    stress<monoid_min<int>>(rng, [](int a, int b) { return std::min(a, b); });
    {
        persistent_segtree<monoid_add<int>> seg(0);
        assert(seg.all_prod(0) == 0 && seg.prod(0, 0, 0) == 0);
        persistent_segtree<monoid_add<int>> seg1(3);
        int r = seg1.set(0, 1, 5);
        assert(seg1.all_prod(0) == 0 && seg1.all_prod(r) == 5 && seg1.prod(r, 1, 2) == 5);
    }
    {
        int n = 200000, q = 200000;
        auto start = std::chrono::steady_clock::now();
        persistent_segtree<monoid_add<long long>> seg(n);
        std::vector<int> roots{0};
        long long acc = 0;
        for (int i = 0; i < q; i++) {
            int k = rng() % roots.size();
            roots.push_back(seg.set(roots[k], rng() % n, rng() % 1000));
            int l = rng() % n, r = rng() % n;
            if (l > r) std::swap(l, r);
            acc += seg.prod(roots[rng() % roots.size()], l, r + 1);
        }
        auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
        std::cerr << "perf n=q=" << n << ": " << ms << " ms (" << acc % 1000 << ")\n";
    }
    std::cout << "Hello World\n";
}
#line 1 "test/unit/persistent_segtree.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

#line 2 "algebra/monoid_add.hpp"
template <class T>
struct monoid_add {
    using S = T;
    static S op(S a, S b) {
        return a + b;
    }
    static S e() {
        return T(0);
    }
};
#line 3 "algebra/monoid_min.hpp"
#include <limits>
template <class T>
struct monoid_min {
    using S = T;
    static S op(S a, S b) {
        return std::min(a, b);
    }
    static S e() {
        return std::numeric_limits<T>::max();
    }
};
#line 4 "datastructure/persistent_segtree.hpp"

#line 2 "algebra/concept.hpp"
#include <concepts>
template <class M>
concept semigroup = requires(typename M::S a, typename M::S b) {
    { M::op(a, b) } -> std::same_as<typename M::S>;
};
template <class M>
concept monoid = semigroup<M> && requires {
    { M::e() } -> std::same_as<typename M::S>;
};
template <class G>
concept group = monoid<G> && requires(typename G::S a) {
    { G::inv(a) } -> std::same_as<typename G::S>;
};
template <class A>
concept action = requires(typename A::F f, typename A::F g) {
    { A::composition(f, g) } -> std::same_as<typename A::F>;
    { A::id() } -> std::same_as<typename A::F>;
    { A::composition_commutative } -> std::convertible_to<bool>;
};
template <class A>
concept acted_monoid = monoid<A> && action<A> && requires(typename A::S x, typename A::F f) {
    { A::mapping(f, x) } -> std::same_as<typename A::S>;
};
template <class R>
concept semiring = requires(typename R::S a, typename R::S b) {
    { R::add(a, b) } -> std::same_as<typename R::S>;
    { R::zero() } -> std::same_as<typename R::S>;
    { R::mul(a, b) } -> std::same_as<typename R::S>;
    { R::one() } -> std::same_as<typename R::S>;
};
template <class A>
concept beats_acted_monoid = acted_monoid<A> && requires(typename A::S x) {
    { x.fail } -> std::convertible_to<bool>;
};
#line 6 "datastructure/persistent_segtree.hpp"
template <monoid M> struct persistent_segtree {
public:
    using S = typename M::S;
    explicit persistent_segtree(int n) : persistent_segtree(std::vector<S>(n, M::e())) {
    }
    explicit persistent_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        nodes.reserve(2 * _n);
        if (_n > 0) build(v, 0, _n);
    }
    int size() const {
        return _n;
    }
    S get(int root, int p) const {
        assert(0 <= p && p < _n);
        int cur = root, l = 0, r = _n;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (p < mid) {
                cur = nodes[cur].l, r = mid;
            } else {
                cur = nodes[cur].r, l = mid;
            }
        }
        return nodes[cur].val;
    }
    int set(int root, int p, const S& x) {
        assert(0 <= p && p < _n);
        int res = copy(root);
        int cur = res, l = 0, r = _n;
        path.clear();
        while (r - l > 1) {
            path.push_back(cur);
            int mid = (l + r) / 2;
            if (p < mid) {
                int nxt = copy(nodes[cur].l);
                nodes[cur].l = nxt;
                cur = nxt, r = mid;
            } else {
                int nxt = copy(nodes[cur].r);
                nodes[cur].r = nxt;
                cur = nxt, l = mid;
            }
        }
        nodes[cur].val = x;
        for (int i = int(path.size()) - 1; i >= 0; i--) {
            node& v = nodes[path[i]];
            v.val = M::op(nodes[v.l].val, nodes[v.r].val);
        }
        return res;
    }
    S prod(int root, int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        return prod(root, 0, _n, l, r);
    }
    S all_prod(int root) const {
        return _n == 0 ? M::e() : nodes[root].val;
    }

private:
    struct node {
        int l, r;
        S val;
    };
    int _n;
    std::vector<node> nodes;
    std::vector<int> path;
    int copy(int v) {
        nodes.push_back(nodes[v]);
        return int(nodes.size()) - 1;
    }
    int build(const std::vector<S>& v, int l, int r) {
        if (r - l == 1) {
            nodes.push_back({-1, -1, v[l]});
            return int(nodes.size()) - 1;
        }
        int mid = (l + r) / 2;
        int res = int(nodes.size());
        nodes.push_back({-1, -1, M::e()});
        int lc = build(v, l, mid);
        int rc = build(v, mid, r);
        nodes[res].l = lc, nodes[res].r = rc;
        nodes[res].val = M::op(nodes[lc].val, nodes[rc].val);
        return res;
    }
    S prod(int cur, int nl, int nr, int l, int r) const {
        if (r <= nl || nr <= l) return M::e();
        if (l <= nl && nr <= r) return nodes[cur].val;
        int mid = (nl + nr) / 2;
        return M::op(prod(nodes[cur].l, nl, mid, l, r), prod(nodes[cur].r, mid, nr, l, r));
    }
};
#line 12 "test/unit/persistent_segtree.test.cpp"
template <class M, class Naive>
void stress(std::mt19937_64& rng, const Naive& naive) {
    using S = typename M::S;
    for (int iter = 0; iter < 200; iter++) {
        int n = 1 + rng() % 20;
        std::vector<S> init(n);
        for (auto& x : init) x = S(rng() % 100);
        persistent_segtree<M> seg(init);
        std::vector<std::vector<S>> versions{init};
        std::vector<int> roots{0};
        assert(seg.size() == n);
        for (int t = 0; t < 60; t++) {
            int k = rng() % roots.size();
            int p = rng() % n;
            S x = S(rng() % 100);
            roots.push_back(seg.set(roots[k], p, x));
            std::vector<S> v = versions[k];
            v[p] = x;
            versions.push_back(v);
            int c = rng() % roots.size();
            for (int i = 0; i < n; i++) assert(seg.get(roots[c], i) == versions[c][i]);
            for (int l = 0; l <= n; l++) {
                for (int r = l; r <= n; r++) {
                    S expect = M::e();
                    for (int i = l; i < r; i++) expect = naive(expect, versions[c][i]);
                    assert(seg.prod(roots[c], l, r) == expect);
                }
            }
            assert(seg.all_prod(roots[c]) == seg.prod(roots[c], 0, n));
        }
    }
}
int main() {
    std::mt19937_64 rng(20261027);
    stress<monoid_add<long long>>(rng, [](long long a, long long b) { return a + b; });
    stress<monoid_min<int>>(rng, [](int a, int b) { return std::min(a, b); });
    {
        persistent_segtree<monoid_add<int>> seg(0);
        assert(seg.all_prod(0) == 0 && seg.prod(0, 0, 0) == 0);
        persistent_segtree<monoid_add<int>> seg1(3);
        int r = seg1.set(0, 1, 5);
        assert(seg1.all_prod(0) == 0 && seg1.all_prod(r) == 5 && seg1.prod(r, 1, 2) == 5);
    }
    {
        int n = 200000, q = 200000;
        auto start = std::chrono::steady_clock::now();
        persistent_segtree<monoid_add<long long>> seg(n);
        std::vector<int> roots{0};
        long long acc = 0;
        for (int i = 0; i < q; i++) {
            int k = rng() % roots.size();
            roots.push_back(seg.set(roots[k], rng() % n, rng() % 1000));
            int l = rng() % n, r = rng() % n;
            if (l > r) std::swap(l, r);
            acc += seg.prod(roots[rng() % roots.size()], l, r + 1);
        }
        auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
        std::cerr << "perf n=q=" << n << ": " << ms << " ms (" << acc % 1000 << ")\n";
    }
    std::cout << "Hello World\n";
}
Back to top page