library

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

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/monoid.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 <numeric>
#include <random>
#include <vector>

#include "algebra/range_add_range_sum.hpp"
#include "datastructure/lazy_segtree.hpp"
#include "datastructure/segtree.hpp"
#include "algebra/monoid_add.hpp"
#include "algebra/monoid_affine.hpp"
#include "algebra/monoid_argmax.hpp"
#include "algebra/monoid_argmin.hpp"
#include "algebra/monoid_gcd.hpp"
#include "algebra/monoid_max.hpp"
#include "algebra/monoid_min.hpp"
#include "algebra/monoid_xor.hpp"
template <class M, class Naive>
void stress_monoid(std::mt19937 &rng, const Naive &naive) {
    using S = typename M::S;
    const int N = 1 + rng() % 30;
    std::vector<S> a(N);
    for (auto &x : a) x = S(rng() % 100);
    segtree<M> seg(a);
    for (int it = 0; it < 200; it++) {
        if (rng() % 2) {
            int p = rng() % N;
            a[p] = S(rng() % 100);
            seg.set(p, a[p]);
        } else {
            int l = rng() % (N + 1), r = rng() % (N + 1);
            if (l > r) std::swap(l, r);
            S expect = M::e();
            for (int i = l; i < r; i++) expect = naive(expect, a[i]);
            assert(seg.prod(l, r) == expect);
        }
    }
}
template <class M, class Naive>
void stress_argmonoid(std::mt19937 &rng, const Naive &better) {
    using S = typename M::S;
    const int N = 1 + rng() % 30;
    std::vector<S> a(N);
    for (int i = 0; i < N; i++) a[i] = {int(rng() % 5), i};
    segtree<M> seg(a);
    for (int it = 0; it < 200; it++) {
        if (rng() % 2) {
            int p = rng() % N;
            a[p] = {int(rng() % 5), p};
            seg.set(p, a[p]);
        } else {
            int l = rng() % (N + 1), r = rng() % (N + 1);
            if (l > r) std::swap(l, r);
            S got = seg.prod(l, r);
            if (l == r) {
                assert(got.id == -1);
                continue;
            }
            int best = l;
            for (int i = l + 1; i < r; i++) {
                if (better(a[i].val, a[best].val)) best = i;
            }
            assert(got.id == best && got.val == a[best].val);
        }
    }
}
void stress_affine(std::mt19937 &rng) {
    using M = monoid_affine<long long>;
    constexpr long long MOD = 998244353;
    const int N = 1 + rng() % 30;
    std::vector<M::S> a(N);
    for (auto &f : a) f = {(long long)(rng() % 5), (long long)(rng() % 5)};
    segtree<M> seg(a);
    for (int it = 0; it < 200; it++) {
        if (rng() % 2) {
            int p = rng() % N;
            a[p] = {(long long)(rng() % 5), (long long)(rng() % 5)};
            seg.set(p, a[p]);
        } else {
            int l = rng() % (N + 1), r = rng() % (N + 1);
            if (l > r) std::swap(l, r);
            long long x = rng() % 10, y = x;
            for (int i = l; i < r; i++) y = M::eval(a[i], y) % MOD;
            assert(M::eval(seg.prod(l, r), x) % MOD == y);
        }
    }
}
void stress_range_add_range_sum(std::mt19937 &rng) {
    using A = range_add_range_sum<long long>;
    const int N = 1 + rng() % 30;
    std::vector<long long> a(N);
    std::vector<A::S> init(N);
    for (int i = 0; i < N; i++) {
        a[i] = rng() % 100;
        init[i] = A::from(a[i]);
    }
    lazy_segtree<A> seg(init);
    for (int it = 0; it < 200; it++) {
        int l = rng() % (N + 1), r = rng() % (N + 1);
        if (l > r) std::swap(l, r);
        if (rng() % 2) {
            long long x = rng() % 100;
            for (int i = l; i < r; i++) a[i] += x;
            seg.apply(l, r, x);
        } else {
            long long expect = 0;
            for (int i = l; i < r; i++) expect += a[i];
            assert(seg.prod(l, r).sum == expect);
            assert(seg.prod(l, r).len == r - l);
        }
    }
}
int main() {
    std::mt19937 rng(7959);
    for (int trial = 0; trial < 100; trial++) {
        stress_monoid<monoid_add<long long>>(rng, [](long long a, long long b) { return a + b; });
        stress_monoid<monoid_min<int>>(rng, [](int a, int b) { return std::min(a, b); });
        stress_monoid<monoid_max<int>>(rng, [](int a, int b) { return std::max(a, b); });
        stress_monoid<monoid_gcd<int>>(rng, [](int a, int b) { return std::gcd(a, b); });
        stress_monoid<monoid_xor<unsigned>>(rng, [](unsigned a, unsigned b) { return a ^ b; });
        stress_argmonoid<monoid_argmin<int>>(rng, [](int a, int b) { return a < b; });
        stress_argmonoid<monoid_argmax<int>>(rng, [](int a, int b) { return a > b; });
        stress_affine(rng);
        stress_range_add_range_sum(rng);
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}
#line 1 "test/unit/monoid.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#line 2 "algebra/range_add_range_sum.hpp"
template <class T>
struct range_add_range_sum {
    struct S {
        T sum;
        int len;
    };
    using F = T;
    static S op(S a, S b) {
        return {a.sum + b.sum, a.len + b.len};
    }
    static S e() {
        return {T(0), 0};
    }
    static S mapping(F f, S x) {
        return {x.sum + f * x.len, x.len};
    }
    static F composition(F f, F g) {
        return f + g;
    }
    static F id() {
        return T(0);
    }
    static constexpr bool composition_commutative = true;
    static S from(T v) {
        return {v, 1};
    }
};
#line 2 "datastructure/lazy_segtree.hpp"
#include <atcoder/lazysegtree>

#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>;
};
#line 5 "datastructure/lazy_segtree.hpp"
template <acted_monoid A>
using lazy_segtree = atcoder::lazy_segtree<typename A::S, A::op, A::e, typename A::F, A::mapping, A::composition, A::id>;
#line 2 "datastructure/segtree.hpp"
#include <atcoder/segtree>

#line 5 "datastructure/segtree.hpp"
template <monoid M>
using segtree = atcoder::segtree<typename M::S, M::op, M::e>;
#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_argmax.hpp"
#include <limits>
template <class T>
struct monoid_argmax {
    struct S {
        T val;
        int id;
    };
    static S op(S a, S b) {
        if (a.val != b.val) return a.val > b.val ? a : b;
        return a.id < b.id ? a : b;
    }
    static S e() {
        return {std::numeric_limits<T>::lowest(), -1};
    }
};
#line 3 "algebra/monoid_argmin.hpp"
template <class T>
struct monoid_argmin {
    struct S {
        T val;
        int id;
    };
    static S op(S a, S b) {
        if (a.val != b.val) return a.val < b.val ? a : b;
        return a.id < b.id ? a : b;
    }
    static S e() {
        return {std::numeric_limits<T>::max(), -1};
    }
};
#line 3 "algebra/monoid_gcd.hpp"
template <class T>
struct monoid_gcd {
    using S = T;
    static S op(S a, S b) {
        return std::gcd(a, b);
    }
    static S e() {
        return T(0);
    }
};
#line 2 "algebra/monoid_max.hpp"
#include <algorithm>
#line 4 "algebra/monoid_max.hpp"
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 4 "algebra/monoid_min.hpp"
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 2 "algebra/monoid_xor.hpp"
template <class T>
struct monoid_xor {
    using S = T;
    static S op(S a, S b) {
        return a ^ b;
    }
    static S e() {
        return T(0);
    }
};
#line 19 "test/unit/monoid.test.cpp"
template <class M, class Naive>
void stress_monoid(std::mt19937 &rng, const Naive &naive) {
    using S = typename M::S;
    const int N = 1 + rng() % 30;
    std::vector<S> a(N);
    for (auto &x : a) x = S(rng() % 100);
    segtree<M> seg(a);
    for (int it = 0; it < 200; it++) {
        if (rng() % 2) {
            int p = rng() % N;
            a[p] = S(rng() % 100);
            seg.set(p, a[p]);
        } else {
            int l = rng() % (N + 1), r = rng() % (N + 1);
            if (l > r) std::swap(l, r);
            S expect = M::e();
            for (int i = l; i < r; i++) expect = naive(expect, a[i]);
            assert(seg.prod(l, r) == expect);
        }
    }
}
template <class M, class Naive>
void stress_argmonoid(std::mt19937 &rng, const Naive &better) {
    using S = typename M::S;
    const int N = 1 + rng() % 30;
    std::vector<S> a(N);
    for (int i = 0; i < N; i++) a[i] = {int(rng() % 5), i};
    segtree<M> seg(a);
    for (int it = 0; it < 200; it++) {
        if (rng() % 2) {
            int p = rng() % N;
            a[p] = {int(rng() % 5), p};
            seg.set(p, a[p]);
        } else {
            int l = rng() % (N + 1), r = rng() % (N + 1);
            if (l > r) std::swap(l, r);
            S got = seg.prod(l, r);
            if (l == r) {
                assert(got.id == -1);
                continue;
            }
            int best = l;
            for (int i = l + 1; i < r; i++) {
                if (better(a[i].val, a[best].val)) best = i;
            }
            assert(got.id == best && got.val == a[best].val);
        }
    }
}
void stress_affine(std::mt19937 &rng) {
    using M = monoid_affine<long long>;
    constexpr long long MOD = 998244353;
    const int N = 1 + rng() % 30;
    std::vector<M::S> a(N);
    for (auto &f : a) f = {(long long)(rng() % 5), (long long)(rng() % 5)};
    segtree<M> seg(a);
    for (int it = 0; it < 200; it++) {
        if (rng() % 2) {
            int p = rng() % N;
            a[p] = {(long long)(rng() % 5), (long long)(rng() % 5)};
            seg.set(p, a[p]);
        } else {
            int l = rng() % (N + 1), r = rng() % (N + 1);
            if (l > r) std::swap(l, r);
            long long x = rng() % 10, y = x;
            for (int i = l; i < r; i++) y = M::eval(a[i], y) % MOD;
            assert(M::eval(seg.prod(l, r), x) % MOD == y);
        }
    }
}
void stress_range_add_range_sum(std::mt19937 &rng) {
    using A = range_add_range_sum<long long>;
    const int N = 1 + rng() % 30;
    std::vector<long long> a(N);
    std::vector<A::S> init(N);
    for (int i = 0; i < N; i++) {
        a[i] = rng() % 100;
        init[i] = A::from(a[i]);
    }
    lazy_segtree<A> seg(init);
    for (int it = 0; it < 200; it++) {
        int l = rng() % (N + 1), r = rng() % (N + 1);
        if (l > r) std::swap(l, r);
        if (rng() % 2) {
            long long x = rng() % 100;
            for (int i = l; i < r; i++) a[i] += x;
            seg.apply(l, r, x);
        } else {
            long long expect = 0;
            for (int i = l; i < r; i++) expect += a[i];
            assert(seg.prod(l, r).sum == expect);
            assert(seg.prod(l, r).len == r - l);
        }
    }
}
int main() {
    std::mt19937 rng(7959);
    for (int trial = 0; trial < 100; trial++) {
        stress_monoid<monoid_add<long long>>(rng, [](long long a, long long b) { return a + b; });
        stress_monoid<monoid_min<int>>(rng, [](int a, int b) { return std::min(a, b); });
        stress_monoid<monoid_max<int>>(rng, [](int a, int b) { return std::max(a, b); });
        stress_monoid<monoid_gcd<int>>(rng, [](int a, int b) { return std::gcd(a, b); });
        stress_monoid<monoid_xor<unsigned>>(rng, [](unsigned a, unsigned b) { return a ^ b; });
        stress_argmonoid<monoid_argmin<int>>(rng, [](int a, int b) { return a < b; });
        stress_argmonoid<monoid_argmax<int>>(rng, [](int a, int b) { return a > b; });
        stress_affine(rng);
        stress_range_add_range_sum(rng);
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}
Back to top page