library

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

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/dynamic_segtree.test.cpp

Depends on

Code

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

#include "algebra/monoid_add.hpp"
#include "algebra/monoid_affine.hpp"
#include "algebra/monoid_max.hpp"
#include "datastructure/dynamic_segtree.hpp"
bool at_most_10(long long x) {
    return x <= 10;
}
void stress_small(std::mt19937& rng) {
    const long long lo = -(long long)(rng() % 20), hi = lo + 1 + rng() % 40;
    const long long n = hi - lo;
    std::vector<long long> a(n, 0);
    dynamic_segtree<monoid_add<long long>> seg(lo, hi);
    for (int it = 0; it < 300; it++) {
        int type = rng() % 5;
        if (type == 0) {
            long long p = lo + rng() % n;
            long long x = rng() % 5;
            a[p - lo] = x;
            seg.set(p, x);
        } else if (type == 1) {
            long long p = lo + rng() % n;
            assert(seg.get(p) == a[p - lo]);
        } else if (type == 2) {
            long long l = lo + rng() % (n + 1), r = lo + rng() % (n + 1);
            if (l > r) std::swap(l, r);
            long long expect = 0;
            for (long long i = l; i < r; i++) expect += a[i - lo];
            assert(seg.prod(l, r) == expect);
        } else if (type == 3) {
            long long l = lo + rng() % (n + 1);
            long long k = rng() % 15;
            long long r = l, sum = 0;
            while (r < hi && sum + a[r - lo] <= k) sum += a[r - lo], r++;
            assert(seg.max_right(l, [&](long long x) { return x <= k; }) == r);
            if (k == 10) assert(seg.max_right<at_most_10>(l) == r);
        } else {
            long long r = lo + rng() % (n + 1);
            long long k = rng() % 15;
            long long l = r, sum = 0;
            while (l > lo && sum + a[l - 1 - lo] <= k) sum += a[l - 1 - lo], l--;
            assert(seg.min_left(r, [&](long long x) { return x <= k; }) == l);
        }
    }
    long long total = 0;
    for (long long x : a) total += x;
    assert(seg.all_prod() == total);
}
void stress_wide(std::mt19937& rng) {
    dynamic_segtree<monoid_max<long long>> seg;
    std::map<long long, long long> a;
    const long long lim = 1LL << 62;
    for (int it = 0; it < 300; it++) {
        long long p = (long long)(rng() % (2 * (unsigned long long)lim)) - lim;
        if (rng() % 2) p = (long long)(rng() % 100) - 50;
        if (rng() % 2) {
            long long x = rng() % 1000;
            a[p] = x;
            seg.set(p, x);
        } else {
            long long q = (long long)(rng() % (2 * (unsigned long long)lim)) - lim;
            long long l = std::min(p, q), r = std::max(p, q) + 1;
            long long expect = monoid_max<long long>::e();
            for (auto it2 = a.lower_bound(l); it2 != a.end() && it2->first < r; ++it2) expect = std::max(expect, it2->second);
            assert(seg.prod(l, r) == expect);
        }
    }
}
void stress_noncommutative(std::mt19937& rng) {
    using M = monoid_affine<long long>;
    const long long n = 1 + rng() % 30;
    std::vector<M::S> a(n, M::e());
    dynamic_segtree<M> seg(0, n);
    for (int it = 0; it < 200; it++) {
        if (rng() % 2) {
            long long p = rng() % n;
            a[p] = {(long long)(rng() % 3), (long long)(rng() % 3)};
            seg.set(p, a[p]);
        } else {
            long long l = rng() % (n + 1), r = rng() % (n + 1);
            if (l > r) std::swap(l, r);
            M::S expect = M::e();
            for (long long i = l; i < r; i++) expect = M::op(expect, a[i]);
            M::S got = seg.prod(l, r);
            assert(M::eval(got, 7) == M::eval(expect, 7));
        }
    }
}
int main() {
    std::mt19937 rng(20261028);
    for (int trial = 0; trial < 100; trial++) {
        stress_small(rng);
        stress_wide(rng);
        stress_noncommutative(rng);
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}
#line 1 "test/unit/dynamic_segtree.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include <map>
#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 2 "algebra/monoid_affine.hpp"
template <class T>
struct monoid_affine {
    struct S {
        T a, b;
    };
    static S op(S f, S g) {
        return {g.a * f.a, g.a * f.b + g.b};
    }
    static S e() {
        return {T(1), T(0)};
    }
    static T eval(S f, T x) {
        return f.a * x + f.b;
    }
};
#line 2 "algebra/monoid_max.hpp"
#include <algorithm>
#include <limits>
template <class T>
struct monoid_max {
    using S = T;
    static S op(S a, S b) {
        return std::max(a, b);
    }
    static S e() {
        return std::numeric_limits<T>::lowest();
    }
};
#line 3 "datastructure/dynamic_segtree.hpp"
#include <utility>
#line 5 "datastructure/dynamic_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 7 "datastructure/dynamic_segtree.hpp"
template <monoid M> struct dynamic_segtree {
public:
    using S = typename M::S;
    explicit dynamic_segtree(long long lo = -(1LL << 62), long long hi = 1LL << 62) : lo(lo), hi(hi) {
        assert(lo < hi);
    }
    void set(long long p, S x) {
        assert(lo <= p && p < hi);
        root = set(root, lo, hi, p, x);
    }
    S get(long long p) const {
        assert(lo <= p && p < hi);
        int t = root;
        long long a = lo, b = hi;
        while (t != -1) {
            if (nodes[t].idx == p) return nodes[t].val;
            long long c = mid(a, b);
            if (p < c) {
                t = nodes[t].l, b = c;
            } else {
                t = nodes[t].r, a = c;
            }
        }
        return M::e();
    }
    S prod(long long l, long long r) const {
        assert(lo <= l && l <= r && r <= hi);
        return prod(root, lo, hi, l, r);
    }
    S all_prod() const {
        return root == -1 ? M::e() : nodes[root].prod;
    }
    template <bool (*f)(S)> long long max_right(long long l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> long long max_right(long long l, F f) const {
        assert(lo <= l && l <= hi);
        S product = M::e();
        assert(f(product));
        return max_right(root, lo, hi, l, f, product);
    }
    template <bool (*f)(S)> long long min_left(long long r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> long long min_left(long long r, F f) const {
        assert(lo <= r && r <= hi);
        S product = M::e();
        assert(f(product));
        return min_left(root, lo, hi, r, f, product);
    }

private:
    struct node {
        long long idx;
        S val, prod;
        int l = -1, r = -1;
    };
    long long lo, hi;
    int root = -1;
    std::vector<node> nodes;
    static long long mid(long long a, long long b) {
        return a + (long long)(((unsigned long long)b - (unsigned long long)a) / 2);
    }
    void update(int t) {
        node& v = nodes[t];
        S res = v.l == -1 ? v.val : M::op(nodes[v.l].prod, v.val);
        v.prod = v.r == -1 ? res : M::op(res, nodes[v.r].prod);
    }
    int set(int t, long long a, long long b, long long p, S x) {
        if (t == -1) {
            nodes.push_back({p, x, x});
            return int(nodes.size()) - 1;
        }
        if (nodes[t].idx == p) {
            nodes[t].val = x;
            update(t);
            return t;
        }
        long long c = mid(a, b);
        if (p < c) {
            if (nodes[t].idx < p) std::swap(nodes[t].idx, p), std::swap(nodes[t].val, x);
            int child = set(nodes[t].l, a, c, p, x);
            nodes[t].l = child;
        } else {
            if (p < nodes[t].idx) std::swap(nodes[t].idx, p), std::swap(nodes[t].val, x);
            int child = set(nodes[t].r, c, b, p, x);
            nodes[t].r = child;
        }
        update(t);
        return t;
    }
    S prod(int t, long long a, long long b, long long l, long long r) const {
        if (t == -1 || b <= l || r <= a) return M::e();
        const node& v = nodes[t];
        if (l <= a && b <= r) return v.prod;
        long long c = mid(a, b);
        S res = prod(v.l, a, c, l, r);
        if (l <= v.idx && v.idx < r) res = M::op(res, v.val);
        return M::op(res, prod(v.r, c, b, l, r));
    }
    template <class F>
    long long max_right(int t, long long a, long long b, long long l, const F& f, S& product) const {
        if (t == -1 || b <= l) return hi;
        const node& v = nodes[t];
        if (l <= a && f(M::op(product, v.prod))) {
            product = M::op(product, v.prod);
            return hi;
        }
        long long c = mid(a, b);
        long long res = max_right(v.l, a, c, l, f, product);
        if (res != hi) return res;
        if (l <= v.idx) {
            product = M::op(product, v.val);
            if (!f(product)) return v.idx;
        }
        return max_right(v.r, c, b, l, f, product);
    }
    template <class F>
    long long min_left(int t, long long a, long long b, long long r, const F& f, S& product) const {
        if (t == -1 || r <= a) return lo;
        const node& v = nodes[t];
        if (b <= r && f(M::op(v.prod, product))) {
            product = M::op(v.prod, product);
            return lo;
        }
        long long c = mid(a, b);
        long long res = min_left(v.r, c, b, r, f, product);
        if (res != lo) return res;
        if (v.idx < r) {
            product = M::op(v.val, product);
            if (!f(product)) return v.idx + 1;
        }
        return min_left(v.l, a, c, r, f, product);
    }
};
#line 12 "test/unit/dynamic_segtree.test.cpp"
bool at_most_10(long long x) {
    return x <= 10;
}
void stress_small(std::mt19937& rng) {
    const long long lo = -(long long)(rng() % 20), hi = lo + 1 + rng() % 40;
    const long long n = hi - lo;
    std::vector<long long> a(n, 0);
    dynamic_segtree<monoid_add<long long>> seg(lo, hi);
    for (int it = 0; it < 300; it++) {
        int type = rng() % 5;
        if (type == 0) {
            long long p = lo + rng() % n;
            long long x = rng() % 5;
            a[p - lo] = x;
            seg.set(p, x);
        } else if (type == 1) {
            long long p = lo + rng() % n;
            assert(seg.get(p) == a[p - lo]);
        } else if (type == 2) {
            long long l = lo + rng() % (n + 1), r = lo + rng() % (n + 1);
            if (l > r) std::swap(l, r);
            long long expect = 0;
            for (long long i = l; i < r; i++) expect += a[i - lo];
            assert(seg.prod(l, r) == expect);
        } else if (type == 3) {
            long long l = lo + rng() % (n + 1);
            long long k = rng() % 15;
            long long r = l, sum = 0;
            while (r < hi && sum + a[r - lo] <= k) sum += a[r - lo], r++;
            assert(seg.max_right(l, [&](long long x) { return x <= k; }) == r);
            if (k == 10) assert(seg.max_right<at_most_10>(l) == r);
        } else {
            long long r = lo + rng() % (n + 1);
            long long k = rng() % 15;
            long long l = r, sum = 0;
            while (l > lo && sum + a[l - 1 - lo] <= k) sum += a[l - 1 - lo], l--;
            assert(seg.min_left(r, [&](long long x) { return x <= k; }) == l);
        }
    }
    long long total = 0;
    for (long long x : a) total += x;
    assert(seg.all_prod() == total);
}
void stress_wide(std::mt19937& rng) {
    dynamic_segtree<monoid_max<long long>> seg;
    std::map<long long, long long> a;
    const long long lim = 1LL << 62;
    for (int it = 0; it < 300; it++) {
        long long p = (long long)(rng() % (2 * (unsigned long long)lim)) - lim;
        if (rng() % 2) p = (long long)(rng() % 100) - 50;
        if (rng() % 2) {
            long long x = rng() % 1000;
            a[p] = x;
            seg.set(p, x);
        } else {
            long long q = (long long)(rng() % (2 * (unsigned long long)lim)) - lim;
            long long l = std::min(p, q), r = std::max(p, q) + 1;
            long long expect = monoid_max<long long>::e();
            for (auto it2 = a.lower_bound(l); it2 != a.end() && it2->first < r; ++it2) expect = std::max(expect, it2->second);
            assert(seg.prod(l, r) == expect);
        }
    }
}
void stress_noncommutative(std::mt19937& rng) {
    using M = monoid_affine<long long>;
    const long long n = 1 + rng() % 30;
    std::vector<M::S> a(n, M::e());
    dynamic_segtree<M> seg(0, n);
    for (int it = 0; it < 200; it++) {
        if (rng() % 2) {
            long long p = rng() % n;
            a[p] = {(long long)(rng() % 3), (long long)(rng() % 3)};
            seg.set(p, a[p]);
        } else {
            long long l = rng() % (n + 1), r = rng() % (n + 1);
            if (l > r) std::swap(l, r);
            M::S expect = M::e();
            for (long long i = l; i < r; i++) expect = M::op(expect, a[i]);
            M::S got = seg.prod(l, r);
            assert(M::eval(got, 7) == M::eval(expect, 7));
        }
    }
}
int main() {
    std::mt19937 rng(20261028);
    for (int trial = 0; trial < 100; trial++) {
        stress_small(rng);
        stress_wide(rng);
        stress_noncommutative(rng);
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}
Back to top page